描述

想必你肯定已经遇到过汉诺塔问题：不同大小的木质圆盘堆叠在三根柱子上，最初，所有圆盘都按大小顺序堆叠在同一根柱子上，最大的圆盘在底部。目标是将整个圆盘塔转移到另外两根柱子中的某一根上，每次只能移动一个圆盘，并且永远不能把较大的圆盘放在较小的圆盘上面。 根据一个古老的传说，一座古老的西藏寺院里的僧侣们数千年来一直在尝试解决一个特别大的汉诺塔问题实例，这个实例有 $47$个圆盘。由于这至少需要$2 ^47 −1$次移动，而且僧侣们一开始没有策略，他们在仍然遵循规则的情况下把一切都弄乱了。现在他们想用最少的移动次数将圆盘整齐地堆叠在任意一根柱子上。但他们都发过誓，禁止违反规则移动圆盘。他们想知道把圆盘堆叠在哪根柱子上是最好的，以及所需的最少移动次数。

编写一个程序来为这些僧侣解决这个问题。你的程序还应该能够处理任意数量$N（0<N≤100000）$的圆盘。计算中涉及的数字可能会变得相当大。因此，僧侣们只对移动次数取模$1000000$的结果感兴趣。 

示例

下面这个示例可以在4次移动内解决。 输入 输入文件hanoi.in的第一行包含圆盘的数量$N（N≤100000）$。 第二行包含三个整数

$s1,s2,s3$，满足$0≤s1s2<s3≤N$且s1+s2+s3=N$，即三根柱子上各自圆盘的数量。第三行到第五行每行包含一根柱子上圆盘的大小。更准确地说：

输入文件的第$(i+2)$行由整数$m i,1 ⋯m i,s i$组成，其中$1≤m i,j≤N$，表示第$i$根柱子上圆盘的大小。圆盘是从下往上给出的，因此 m i,1 ​

m i,2 ​ ⋯>m i,s i ​

​

。 请注意，一个空的柱子用一个空行表示。这$N$个圆盘的大小各不相同。所有数字都由一个空格分隔。

输出

输出文件 hanoi.out 的第一行包含数字 d ， d∈{1,2,3} ，表示能够用最少移动次数将圆盘堆叠到的柱子编号。第二行包含所需的移动次数 M 取模 1000000 的结果。 输入数据 1 7 2

1

4 2

1 3 7

6

5

4

输出数据 1

3

4