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

Một thiết bị tính toán cần giải một loạt các bài toán. Có $2$ nhà khoa học, nhà khoa học thứ $i$ mang đến $k_i$ bài toán được đánh số từ $1$ đến $k_i$. Các bài toán của cùng một nhà khoa học phải được giải theo đúng thứ tự $1,2,\dots ,k_i$ (vì mỗi bài phụ thuộc vào kết quả của bài liền trước), nhưng các bài của những nhà khoa học khác nhau có thể xen kẽ tùy ý.

Bài toán thứ $j$ của nhà khoa học thứ $i$ cần $a_{i,j}$ đơn vị tài nguyên. Thiết bị giải lần lượt các bài toán, mỗi lần một bài. Thao tác giải phóng tài nguyên rất chậm, nên ta muốn mỗi bài toán tiếp theo cần không ít hơn tài nguyên so với bài liền trước.

Gọi hai bài toán liên tiếp trong danh sách là một cặp xấu nếu bài đứng trước cần nhiều tài nguyên hơn bài đứng sau. Hãy sắp xếp toàn bộ các bài toán thành một danh sách (giữ đúng thứ tự nội bộ của mỗi nhà khoa học) sao cho số cặp xấu là nhỏ nhất có thể.

Để giảm kích thước dữ liệu, các giá trị $a_{i,j}$ được sinh theo công thức: cho trước $a_{i,1}$ và ba tham số $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.$$

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số nhà khoa học ($n=2$).
• $n$ dòng tiếp theo, dòng thứ $i$ chứa năm số nguyên $k_i,a_{i,1},x_i,y_i,m_i$.

Dữ liệu ra

• Dòng đầu in một số nguyên — số cặp xấu nhỏ nhất.
• Nếu tổng số bài toán không vượt quá $200000$, in thêm mỗi bài toán trên một dòng theo đúng thứ tự đã sắp xếp: hai số nguyên là số đơn vị tài nguyên của bài toán và chỉ số nhà khoa học đã đưa ra bài toán đó (đánh số từ $1$ đến $n$ theo thứ tự nhập vào).

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

Ràng buộc

• $n=2$
• $1\le k_i\le 2·{10}^5$
• $0\le a_{i,1}<m_i\le {10}^9$
• $1\le x_i,y_i\le {10}^9$
• Tổng số bài toán $k_1+k_2\le 4·{10}^5$.

Ví dụ