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

题目描述

徐老师最近在玩《精灵宝可梦》，这天他决定给自己的 $n$ 只宝可梦办一场宝可梦大赛。

众所周知，每只不同的宝可梦有自己的特性和属性，而当它在自己擅长或者适宜的场地中进行战斗时，会有额外的战斗力加成（例如草系的妙蛙种子在草地上战斗时就会获得额外的战斗力加成，雷系的皮卡丘在雷雨天气会有额外的战斗力加成）。

但是由于资金有限，徐老师只准备了三种不同的场地：草地，火山，水池。

为了方便描述，徐老师将这 $n$ 只宝可梦分别在三个场地进行战斗时的战斗力进行了排名，排名越高的宝可梦能力就越强。

例如徐老师现在有 $4$ 只宝可梦，在草地的战斗力排名分别为 $1,2,3,4$，表示如果在草地上战斗，战斗力最高的是 $1$ 号宝可梦，战斗力最低的是 $4$ 号宝可梦。

而每次徐老师会随机指定两只宝可梦，然后随机指定一个场地，让他们进行战斗，在指定场地上战斗力较弱的宝可梦会被淘汰。

徐老师会进行几次询问，每次询问一个编号 $x$，表示他想知道是否存在一种可能出现的战斗顺序，使得 $x$ 号宝可梦能获得 冠军（即其他宝可梦都因为战斗淘汰，最后只留下 $x$ 号宝可梦）

但是徐老师觉得只是询问太简单了，于是他会在询问过程中拿出一些 "学习机器" 给宝可梦使用，这种机器会影响宝可梦的战斗力，你可以简单的理解为，每次使用学习机器，会使得 $a$ 和 $b$ 两只宝可梦在 $c$ 场地中的 排名互换。

例如上面的例子，如果给 $2,4$ 两只宝可梦在草地使用学习机器，那么草地上的战斗力排名会变成 $1,4,3,2$。

输入格式

输入第一行包含一个整数 $n$ 表示宝可梦数量。

输入第二行包含 $n$ 个数字，且一定是 $1 \sim n$ 的一个全排列，表示在草地上所有宝可梦的战斗力排名。

输入第三行包含 $n$ 个数字，且一定是 $1 \sim n$ 的一个全排列，表示在火山上所有宝可梦的战斗力排名。

输入第四行包含 $n$ 个数字，且一定是 $1 \sim n$ 的一个全排列，表示在水池里所有宝可梦的战斗力排名。

输入第五行包含一个整数 $T$ 表示操作次数。

接下来 $T$ 行，每行表示一次询问/使用学习机器的操作，格式如下：

• 1 x：表示询问现在 x 号宝可梦有没有可能获得冠军。
• 2 a b c：表示在 $c$ 号场地交换 $a,b$ 宝可梦的排名，其中 $c=1$ 表示草地，$c=2$ 表示火山，$c=3$ 表示水池。

输出格式

对于每次询问，如果询问宝可梦能获得冠军，则输出 Congratulations!，否则输出 So sad!

数据范围

特别的，保证所有测试点满足：$1 \leq n,T \leq 10^5, 1 \leq a,b,x \leq n, 1 \leq c \leq 3, a \not= b$

样例输入1

4 
1 2 3 4
2 1 3 4
2 4 3 1
4
1 1
1 4
2 1 4 3
1 4

样例输出1

Congratulations!
Congratulations!
So sad!

样例解释1

初始状态下：

• 1 号宝可梦在草地上排名第 1，可以一直在草地上战斗，依次淘汰其余所有宝可梦，成为冠军；
• 4 号宝可梦可以安排如下战斗顺序：先由 1 号在草地上淘汰 2 号（1 号排名 1 < 2 号排名 2），再由 4 号在水池中淘汰 1 号（4 号排名 2 < 1 号排名 4），最后由 4 号在水池中淘汰 3 号（排名 2 < 排名 3），成为冠军。

执行 2 1 4 3 后，4 号在水池中的排名变为第 4，三个场地上的排名均为最后，无法淘汰任何宝可梦，因此不能再夺冠。

样例输入2

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

样例输出2

Congratulations!
So sad!
So sad!
Congratulations!