该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

grs的汉诺塔

时间限制：1s

空间限制：256MB

Description

（出题人：hate_eat_sugar_vinegar_mile_kun)

grs喜欢做一些思维游戏，例如汉诺塔. 某天晚上，grs约你第二天一起散步，为了防止散步时无聊，他打算和你用口述的方式玩汉诺塔。 为了方便，你们制定了如下规则：

grs指定一个数 $N$， 代表开始时，$A，B，C$ 三座汉诺塔上，分别有 $N, 0, 0$ 个盘子。

游戏开始时，对于$A$塔从上到下的第 i (1 ≤  i ≤ n) 个盘子，盘子代表的数值为$2^{i-1}$

为了方便阐述，你们需要按照解决汉诺塔的最优步骤，轮流说出每次移动盘子后，A, B, C三座汉诺塔上，所有盘子的数值的和

同时，你们还需要判断，对方是否算错，如果有人算错，对手没有发现，而前者又突然发现自己算错了，那么算后者输。

简单来说，在本题中，如果你算错了，grs一定会发现你算错了，此时你就输了。grs告诉你，有时他会故意说出错误答案，来试探你能不能发现。如果你发现了他的错误，则需要输出正确的数

特殊地，汉诺塔移动之前的初始状态由你输出，样例中有解释

特殊地，如果最后一次移动盘子后的值由对方输出，你需要判断对方是否正确，如果正确，你需要把对方的正确结果再输出一遍，如果错误，你需要输出正确结果

由于grs是玩这个游戏的高手，而你只是个新手。为了公平，只要你坚持到最后，或者发现他的错误，并加以改正，就算你胜利了。

听到这里，你连忙编一个程序，来应对明天的游戏

Input Format

第一行包含单个整数 $n(1 ≤  n ≤ 16)$ ，即游戏开始时，第 $A$ 座汉诺塔上的盘子数量

以后的几行，每一行都有三个以空格分隔的整数 $a_i$ , $b_i$ ,$c_i$ $(0 ≤ a_i, b_i, c_i ≤ 10^5)$ ，表示grs输出的数

Output Format

每次输出三个整数，数与数之间用空格隔开，分别表示你要输出的 $a_i,b_i,c_i$

Data Range

• $1 \leq  n \leq 20$
• $0 ≤ a_i, b_i, c_i ≤ 10^5$
• 本题意在考察模拟，不会在时空限制上为难你

Input Example #1：

3
6 0 1
4 3 0
1 2 4
0 0 7

Output Example #1：

7 0 0
4 2 1
0 3 4
1 0 6
0 0 7

Input Example #2：

3
6 1 0

Output Example #2：

7 0 0
6 0 1

Note

在样例一中，A塔初始盘子数为3，盘子上的数值分别为1 2 4，和为7。所以你输出7 0 0，按照最优解，下一步把A塔最上面的盘子移到C塔，所以grs输出6 0 1。然后你们轮流输出，直到最后一步，grs输出0 0 7，你需要再输出一遍0 0 7，表示你认为他最后一步答对了

在样例二中，grs输出6 1 0是错误解，你需要输出6 0 1，表示你认为他最后一步答错了