Máy tính của Hải Ly

Có một thiết bị tính toán giải các bài toán lần lượt, từng bài một. Sau khi giải xong một bài và trước khi sang bài tiếp theo, thiết bị phải cấp phát hoặc giải phóng tài nguyên. Thao tác giải phóng tài nguyên rất chậm, vì vậy ta muốn dãy bài toán được sắp xếp sao cho số cặp kề nhau "xấu" là nhỏ nhất, trong đó một cặp $(p,q)$ với $p$ đứng ngay trước $q$ được gọi là xấu nếu $p$ yêu cầu nhiều tài nguyên hơn $q$.

Có $n$ nhà khoa học, nhà khoa học thứ $i$ mang $k_i$ bài toán cần tính, đánh số từ $1$ đến $k_i$. Mỗi bài toán cần một lượng tài nguyên $a_{i,j}$ (đối với bài $j$ của nhà khoa học $i$). Các bài của cùng một nhà khoa học phải được giải theo đúng thứ tự $1,2,\dots ,k_i$.

Để giảm kích thước dữ liệu vào, dãy $a_{i,1},a_{i,2},\dots ,a_{i,k_i}$ được sinh ra theo công thức: cho trước $a_{i,1}$, $x_i$, $y_i$, $m_i$; với mọi $j$ từ $2$ đến $k_i$:

$$a_{i,j}=(a_{i,j-1}·x_i+y_i)mod{m}_i.$$

Hãy sắp xếp tất cả các bài toán của tất cả các nhà khoa học thành một dãy duy nhất sao cho:

• Thứ tự các bài của mỗi nhà khoa học được giữ nguyên (bài $j$ của nhà khoa học $i$ phải đứng trước bài $j+1$ của cùng nhà khoa học đó).
• Số cặp kề nhau xấu trong dãy là nhỏ nhất có thể.

In ra số cặp xấu nhỏ nhất, và nếu tổng số bài không vượt quá $200000$, in thêm thứ tự các bài toán trong cách sắp xếp tối ưu.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số nhà khoa học.
• Mỗi dòng trong $n$ dòng tiếp theo chứa năm số nguyên $k_i,a_{i,1},x_i,y_i,m_i$ — số bài của nhà khoa học $i$ và các tham số sinh dãy.

Dữ liệu ra

• Dòng đầu: số cặp kề nhau xấu nhỏ nhất.
• Nếu tổng $\sum k_i\le 200000$, in thêm $\sum k_i$ dòng, mỗi dòng gồm hai số nguyên: lượng tài nguyên của bài và chỉ số nhà khoa học mang bài đó, theo đúng thứ tự sắp xếp tối ưu.

Nếu có nhiều cách sắp xếp tối ưu, in ra cách bất kỳ.

Ràng buộc

• $1\le n\le 5000$
• $1\le k_i\le 5000$
• $0\le a_{i,1}<m_i\le {10}^9$
• $1\le x_i,y_i\le {10}^9$

Ví dụ