CF207A2.Beaver's Calculator 1.0

The 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.

ABBYY 的聪明海狸再次让我们大吃一惊！他开发了一款新型计算设备，命名为“海狸计算器 1.0”。该设备非常特别，计划用于解决各类科学问题。

为测试该设备，聪明海狸邀请了 $n$ 位科学家，编号为 $1$ 至 $n$。第 $i$ 位科学家带来了 $k_i$ 个计算问题，供该设备处理。第 $i$ 位科学家的问题编号为 $1$ 至 $k_i$，且必须严格按照此顺序依次求解，因为每个问题的求解都高度依赖于前一个问题的计算结果。

每位科学家的每个问题均用一个整数 $a_{i,j}$ 描述，其中 $i$（$1 \le i \le n$）表示科学家编号，$j$（$1 \le j \le k_i$）表示问题编号，而 $a_{i,j}$ 表示该计算设备求解此问题所需的资源单位数。

聪明海狸所开发的计算设备十分独特：它按顺序逐个求解问题。在某个问题求解完毕、下一个问题开始处理之前，该设备会分配或释放资源。

对计算设备而言，释放资源是最昂贵的操作，其速度远慢于分配资源。因此，我们希望：设备处理的每个后续问题所需的资源量不少于前一个问题所需的资源量。

现给出各位科学家所提供的待测问题信息。你需要将所有这些问题重新排列成一个序列，使得该序列中相邻的“不良”问题对的数量尽可能少。我们将序列中两个连续问题称为一个“不良对”，当且仅当前一个问题所需的资源量严格大于后一个问题所需的资源量。注意：同一位科学家的所有问题必须保持原有顺序不变。

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 ≤ 109, 1 ≤ x__i, y__i ≤ 109) — 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.

第一行包含一个整数 $n$ —— 科学家的数量。为减小输入规模，接下来的 $n$ 行中，每行包含五个整数 $k_i$, $a_{i,1}$, $x_i$, $y_i$, $m_i$（其中 $0 \le a_{i,1} < m_i \le 10^9$，$1 \le x_i, y_i \le 10^9$）—— 分别表示第 $i$ 位科学家所拥有的题目数量、第一道题目所需的资源量，以及用于生成后续 $a_{i,j}$ 值的三个参数。对每个 $j$（从 $2$ 到 $k_i$，含端点），需按公式 $a_{i,j} = (a_{i,j-1} \cdot x_i + y_i) \bmod m_i$ 计算 $a_{i,j}$ 的值，其中 $a \bmod b$ 表示 $a$ 除以 $b$ 所得的余数。

若要获得第一组测试用例的全部分数，只需解决满足 $n = 2$ 且 $1 \le k_i \le 2000$ 的情况。

若要获得第二组测试用例的全部分数，只需解决满足 $n = 2$ 且 $1 \le k_i \le 200000$ 的情况。

若要获得第三组测试用例的全部分数，只需解决满足 $1 \le n \le 5000$ 且 $1 \le k_i \le 5000$ 的情况。

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.

第一行输出一个整数——最优排列中“坏”数对的个数。

如果题目总数不超过 200000，则还需输出 行——题目的最优排列顺序。在这些行中的每一行上，输出两个由单个空格分隔的整数：分别为该题所需的资源数量、提出该题的科学家编号。科学家按输入顺序编号为 $1$ 至 $n$。

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.

在第一个样例中，$n = 2$，$k_1 = 2$，$a_{1,1} = 1$，$a_{1,2} = 2$，$k_2 = 2$，$a_{2,1} = 3$，$a_{2,2} = 4$。我们共有两位科学家，每位科学家各有两道计算问题。第一位科学家的问题分别需要 $1$ 和 $2$ 个资源单位，第二位科学家的问题分别需要 $3$ 和 $4$ 个资源单位。我们列出所有可能的计算顺序（每道问题仅由其所需的资源单位数表征）：$(1,\,2,\,3,\,4)$，$(1,\,3,\,2,\,4)$，$(3,\,1,\,2,\,4)$，$(1,\,3,\,4,\,2)$，$(3,\,4,\,1,\,2)$，$(3,\,1,\,4,\,2)$。

问题序列 $(1,\,3,\,2,\,4)$ 包含一个“坏”数对（$3$ 和 $2$），$(3,\,1,\,4,\,2)$ 包含两个“坏”数对（$3$ 和 $1$、$4$ 和 $2$），而 $(1,\,2,\,3,\,4)$ 不包含任何“坏”数对。