这是一个“两次运行”问题。你的程序将被执行两次。

Ivan 的学习成绩很差。在学习期间，他只得了 1 分和 2 分。为了向父母展示他的成绩，他决定使用成绩之和（这样他们就无法识别出他的差成绩了）。Ivan 的成绩可以用一个由字符 '1' 和 '2' 组成的字符串 $s$ 来表示。他开始下载这个字符串，但不幸的是，互联网连接中断了，他只下载了字符串 $s$ 的某个前缀 $s[1..i]$（其中 $1 \le i < |s|$，因此该前缀非空且不等于完整字符串）。重新连接后，字符串的剩余后缀将被下载。

你的程序将被执行两次：

1. 在第一次执行时，你将获得下载的前缀：$s[1..i]$。 你应该输出两个整数 $0 \le d < \min(i + 1, 2000)$ 和 $0 \le info < 2000$。
2. 在第二次执行时，你将获得整数 $info$ 以及字符串的剩余后缀，其中包含了下载前缀的最后 $d$ 个符号：$s[(i + 1 - d)..|s|]$。 你应该输出字符串 $s$ 中所有符号的和。

输入格式

第一行包含一个整数 $type$ ($1 \le type \le 2$)。在第一次执行时，$type = 1$，在第二次执行时，$type = 2$。

输入包含多个独立的测试用例。第二行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。接下来是测试用例的描述。

• 如果 $type = 1$，接下来的 $t$ 行，每行包含一个由字符 '1' 和 '2' 组成的字符串，即下载的前缀 $s[1..i]$。
• 如果 $type = 2$，接下来的 $t$ 行，每行包含一个整数 $info$ ($0 \le info < 2000$)（即你在第一次执行中为该测试用例给出的值），以及一个由字符 '1' 和 '2' 组成的字符串，即该测试用例在第一次执行中给出的 $d$ 所对应的下载后缀 $s[(i + 1 - d)..|s|]$。

保证所有字符串 $s$ 和对应的数字 $i$ 都是预先确定的。 保证所有测试用例的 $|s|$ 之和不超过 $10^6$。 注意，第二次执行时测试用例的顺序可能会被重新排列。

输出格式

• 如果 $type = 1$，对于每个测试用例，你的程序应输出两个整数 $0 \le d < \min(i + 1, 2000)$ 和 $0 \le info < 2000$。这些值将用于该测试用例的第二次执行。
• 如果 $type = 2$，对于每个测试用例，你的程序应输出一个整数，即字符串 $s$ 的总和。

样例

注意，第一次执行时给出的输出仅为示例，你的程序输出可能与之不同。

样例输入 1

1
3
1
222
1212111122

样例输出 1

0 42
1 11
4 22

样例输入 2

2
3
11 22211
22 11222221
42 2

样例输出 2

12
21
3

说明

在第一个测试中，有 3 个测试用例，对应的字符串 $s$ 为： 12 2222211 12121111222221

注意，第二次执行时测试用例的顺序被重新排列了。