每天往返学校时，Detje 都会经过一条有 $N$ 栋房子的街道，房子编号从 $0$ 到 $N - 1$。目前，第 $i$ 栋房子住着第 $i$ 个人。为了换换环境，居民们决定互相交换房子。将要搬进第 $i$ 栋房子的人是第 $a_i$ 个人（目前住在第 $a_i$ 栋房子里）。

每栋房子的花园里都有一个鸟雕像。雕像有两种可能的状态：翅膀要么是张开的（就像鸟在飞），要么是闭合的（就像鸟站在地上）。居民们对鸟雕像的样子有非常强烈的偏好。目前，第 $i$ 栋房子前的鸟处于第 $i$ 位居民偏好的状态。除非雕像被设置为他们偏好的状态，否则居民拒绝搬进房子。Detje 想帮助他们布置鸟雕像，以便他们能够搬家。

为此，她做了以下工作：每当她沿着街道行走（无论是去学校还是回家）时，她都会逐一观察经过的鸟，并可能调整一些雕像（通过张开或闭合它们的翅膀）。由于她在学校和家里的日子非常忙碌，她不记得在之前的步行中看到的鸟的状态。幸运的是，她写下了列表 $a_0, a_1, \dots, a_{N-1}$，所以她知道哪位居民要搬到哪里。

请帮助 Detje 设计一个策略，告诉她应该操纵哪些鸟来将雕像调整到居民喜欢的状态。她最多可以沿着街道走 $60$ 次，但为了获得更高的分数，她应该尽量减少行走的次数。

实现细节

这是一个多次运行的问题，意味着你的程序将被执行多次。

在每次运行中，你应该首先读取一行，包含两个整数 $w$ 和 $N$，分别表示步行的索引和房子的数量。在程序的第一次运行中 $w = 0$，第二次运行中 $w = 1$，依此类推（详情见下文）。

在输入的第二行有 $N$ 个整数 $a_0, a_1, \dots, a_{N-1}$，意味着将要搬进第 $i$ 栋房子的人目前住在第 $a_i$ 栋房子里。$a_i$ 构成了一个排列：即 $0$ 到 $N - 1$ 之间的每个数字在 $a_i$ 列表中恰好出现一次。注意，居民可以选择不搬家；也就是说，允许 $a_i = i$。

居民只会交换一次房子。这意味着对于固定的测试用例，对于你程序的所有运行，$N$ 的值和 $a_i$ 的列表都是相同的。

第一次运行

对于程序的第一次执行，$w = 0$。在此次运行中，你只需输出一个整数 $W$ ($0 \le W \le 60$)，表示你希望 Detje 经过这些房子的次数。然后你的程序应该退出。此后，你的程序将被再次执行 $W$ 次。

后续运行

在程序的下一次运行中，$w = 1$；在之后的一次中 $w = 2$；依此类推，直到最后一次运行 $w = W$。

在你读取了 $w, N$ 和 $a_0, a_1, \dots, a_{N-1}$ 后，Detje 开始沿着街道行走。

• 如果 $w$ 是奇数，Detje 从家走到学校，她将按 $0, 1, \dots, N - 1$ 的顺序经过这些房子。

  你的程序现在应该读取一行 $b_0$，即第 $0$ 栋房子前雕像的当前状态（$0$ 表示闭合，$1$ 表示张开）。在你读取 $b_0$ 后，你应该输出一行，包含 $0$ 或 $1$，即你想要将 $b_0$ 设置为的新值。

  然后你的程序应该读取一行 $b_1$，即第 $1$ 栋房子前雕像的状态；并输出 $b_1$ 的新值。这对每一栋房子都会重复。在 Detje 经过最后一栋房子（即你读取并写入 $b_{N-1}$）后，你的程序应该退出。

  注意，你的程序只能在写入 $b_i$ 的新值后才能读取下一个值 $b_{i+1}$。

• 如果 $w$ 是偶数，Detje 从学校走回家，她将按相反的顺序 $N - 1, N - 2, \dots, 0$ 经过这些房子。也就是说，你从读取和写入 $b_{N-1}$ 开始，然后是 $b_{N-2}$，依此类推，直到 $b_0$。

当 $w = 1$ 时，输入值 $b_0, b_1, \dots, b_{N-1}$ 是鸟雕像的原始状态（这也是居民偏好的状态）。当 $w > 1$ 时，输入到你程序的 $b_0, b_1, \dots, b_{N-1}$ 值将是程序上一次运行将它们设置成的状态。

最后，在程序最后一次运行结束后，对于所有 $i$，必须满足 $b_i$ 的值等于 $b_{a_i}$ 的原始值，否则你将得到错误答案（Wrong Answer）的判决。

说明

如果你的程序 $W + 1$ 次单独运行的总运行时间超过了时间限制，你的提交将被判为时间限制超限（Time Limit Exceeded）。

确保在打印每一行后刷新标准输出，否则你的程序可能会被判为时间限制超限。在 Python 中，只要你使用 input() 读取行，这就会自动发生。在 C++ 中，cout << endl; 除了打印换行符外还会刷新；如果使用 printf，请使用 fflush(stdout)。

数据范围

• $2 \le N \le 500$。
• 你最多可以使用 $W \le 60$ 轮。

你的解决方案将在几组测试用例上进行测试，每组测试用例都有一定的分数。每组测试用例包含一组测试案例。要获得某组测试用例的分数，你需要解决该组中的所有测试案例。

对于你的程序正确解决的每一组测试用例，你将根据以下公式获得分数：

$$\text{score} = S_g \cdot \left(1 - \frac{1}{2} \log_{10}(\max(W_g, 3)/3)\right)$$

其中 $S_g$ 是该组测试用例的最高分，$W_g$ 是该组测试用例中使用的 $W$ 的最大值。你每组测试用例的分数将四舍五入到最接近的整数。

样例

输入格式 1

0 6
1 2 0 4 3 5

输出格式 1

2

输入格式 2

1 6
1 2 0 4 3 5
1
1
0
0
1
0

输出格式 2

1
0
1
1
0
1

输入格式 3

2 6
1 2 0 4 3 5
1
0
1
0
1
1

输出格式 3

0
0
1
1
0
1