Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A3. Beaver's Calculator 1.0

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Smart Beaver from ABBYY has once again surprised us! He has developed a new calculating device, which he called the "Beaver's Calculator 1.0". It is very peculiar and it is planned to be used in a variety of scientific problems.

To test it, the Smart Beaver invited *n* scientists, numbered from 1 to *n*. The *i*-th scientist brought *k*_{i} calculating problems for the device developed by the Smart Beaver from ABBYY. The problems of the *i*-th scientist are numbered from 1 to *k*_{i}, and they must be calculated sequentially in the described order, since calculating each problem heavily depends on the results of calculating of the previous ones.

Each problem of each of the *n* scientists is described by one integer *a*_{i, j}, where *i* (1 ≤ *i* ≤ *n*) is the number of the scientist, *j* (1 ≤ *j* ≤ *k*_{i}) is the number of the problem, and *a*_{i, j} is the number of resource units the calculating device needs to solve this problem.

The calculating device that is developed by the Smart Beaver is pretty unusual. It solves problems sequentially, one after another. After some problem is solved and before the next one is considered, the calculating device allocates or frees resources.

The most expensive operation for the calculating device is freeing resources, which works much slower than allocating them. It is therefore desirable that each next problem for the calculating device requires no less resources than the previous one.

You are given the information about the problems the scientists offered for the testing. You need to arrange these problems in such an order that the number of adjacent "bad" pairs of problems in this list is minimum possible. We will call two consecutive problems in this list a "bad pair" if the problem that is performed first requires more resources than the one that goes after it. Do not forget that the problems of the same scientist must be solved in a fixed order.

Input

The first line contains integer *n* — the number of scientists. To lessen the size of the input, each of the next *n* lines contains five integers *k*_{i}, *a*_{i, 1}, *x*_{i}, *y*_{i}, *m*_{i} (0 ≤ *a*_{i, 1} < *m*_{i} ≤ 10^{9}, 1 ≤ *x*_{i}, *y*_{i} ≤ 10^{9}) — the number of problems of the *i*-th scientist, the resources the first problem requires and three parameters that generate the subsequent values of *a*_{i, j}. For all *j* from 2 to *k*_{i}, inclusive, you should calculate value *a*_{i, j} by formula *a*_{i, j} = (*a*_{i, j - 1} * *x*_{i} + *y*_{i}) *mod* *m*_{i}, where *a* *mod* *b* is the operation of taking the remainder of division of number *a* by number *b*.

To get the full points for the first group of tests it is sufficient to solve the problem with *n* = 2, 1 ≤ *k*_{i} ≤ 2000.

To get the full points for the second group of tests it is sufficient to solve the problem with *n* = 2, 1 ≤ *k*_{i} ≤ 200000.

To get the full points for the third group of tests it is sufficient to solve the problem with 1 ≤ *n* ≤ 5000, 1 ≤ *k*_{i} ≤ 5000.

Output

On the first line print a single number — the number of "bad" pairs in the optimal order.

If the total number of problems does not exceed 200000, also print lines — the optimal order of the problems. On each of these lines print two integers separated by a single space — the required number of resources for the problem and the number of the scientist who offered this problem, respectively. The scientists are numbered from 1 to *n* in the order of input.

Examples

Input

2

2 1 1 1 10

2 3 1 1 10

Output

0

1 1

2 1

3 2

4 2

Input

2

3 10 2 3 1000

3 100 1 999 1000

Output

2

10 1

23 1

49 1

100 2

99 2

98 2

Note

In the first sample *n* = 2, *k*_{1} = 2, *a*_{1, 1} = 1, *a*_{1, 2} = 2, *k*_{2} = 2, *a*_{2, 1} = 3, *a*_{2, 2} = 4. We've got two scientists, each of them has two calculating problems. The problems of the first scientist require 1 and 2 resource units, the problems of the second one require 3 and 4 resource units. Let's list all possible variants of the calculating order (each problem is characterized only by the number of resource units it requires): (1, 2, 3, 4), (1, 3, 2, 4), (3, 1, 2, 4), (1, 3, 4, 2), (3, 4, 1, 2), (3, 1, 4, 2).

Sequence of problems (1, 3, 2, 4) has one "bad" pair (3 and 2), (3, 1, 4, 2) has two "bad" pairs (3 and 1, 4 and 2), and (1, 2, 3, 4) has no "bad" pairs.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/26/2020 23:09:19 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|