#P18861. [Croatian CPC2025] Izgubljeni Input

[Croatian CPC2025] Izgubljeni Input

Izgubljeni Input

题目描述

原来的题目如下:每个场景开始时有一个空序列,依次执行 QQ 次操作。操作有两种:

  • 1 X:向序列末尾加入非负整数 XX,输出操作后整个序列的平均值。
  • 2 A B:向序列末尾加入某个整数(可以为负),使操作后整个序列的平均值为 A/BA/B,输出刚加入的整数。

原题中 0≤X≤1060\le X\le10^6,0≤A/B≤1060\le A/B\le10^6,B>0B>0,且 A,BA,B 互质。第二种操作保证可以加入一个整数来满足要求。

两类操作的答案都以最简分数输出:分子和分母之间用空格分隔,分母为正数。如果答案为整数 YY,则输出 Y 1。

现在原来的输入文件丢失了,只剩下输出文件,以及每个场景的操作次数。你需要根据这些信息,重建任意一份能够产生给定输出的合法输入。

为了方便重建,你输出的操作中,XX 和 A/BA/B 的上限放宽为 101810^{18},其余要求不变。

输入格式

第一行包含整数 TT,表示场景数。

每个场景的第一行包含整数 QQ。

接下来 QQ 行,每行包含两个整数 Ai,BiA_i,B_i,表示原题第 ii 次操作输出的最简分数。你不知道该答案由哪一种操作产生。由题目定义可知 1≤Bi≤i1\le B_i\le i。

给出的答案来自原题的一份合法输入。

输出格式

输出一份重建后的输入文件:

第一行输出 TT。

对于每个场景,先输出 QQ,然后输出 QQ 行操作,每行是以下两种形式之一:

  • 1 X,其中 XX 是整数且 0≤X≤10180\le X\le10^{18}。
  • 2 A B,其中 A,BA,B 是整数,B>0B>0,0≤A/B≤10180\le A/B\le10^{18},且 A,BA,B 互质。执行该操作时,必须能够加入一个整数使平均值变为 A/BA/B。

重建的操作产生的每个答案必须与输入给出的对应答案相同。如果有多种方案,输出任意一种。

数据范围

  • 1≤T≤1041\le T\le10^4,1≤Q≤2×1051\le Q\le2\times10^5。
  • 所有场景的 QQ 之和不超过 2×1052\times10^5。

样例 1

输入

3
5
5 1
4 1
2 1
17 4
3 1
3
6 1
4 1
-9 1
3
6 1
4 1
10 3

输出

3
5
2 5 1
1 3
2 10 3
1 7
2 4 1
3
1 6
2 5 1
2 1 3
3
1 6
1 2
1 2