题目描述

你准备前往传说中的狗狗王国出差，这个王国由 最多64个狗狗部落 组成，每个部落都有自己独特的狗叫声（语言）。幸运的是，你有两名狗狗翻译随行，它们各自掌握若干种汪汪语言。这些语言能力通过十进制数表示，例如，若第一名翻译掌握第1、3、5、6种汪汪语，其能力可表示为十进制数53，即二进制数0011 0101（从右至左第x位为1表示掌握第x种汪汪语）。

注意：为便于理解，样例中采用8个部落进行说明，但实际题目中部落总数n最大为64。

这里假设你和另外两名翻译都会一门不属于这n个部落的通用语（比如人类的语言），可以用这种语言进行内部沟通。

输入格式

• 第一行包含一个整数n（$1 \leq n \leq 64$），表示狗狗部落总数。
• 第二行包含两个整数a和b（$0 \leq a, b \leq 2^n - 1$），分别表示两名翻译的语言能力（十进制数）。
• 第三行包含一个整数m（$1 \leq m \leq n$），表示需要访问的部落数量。
• 第四行包含m个不同的整数$c_1, c_2, \ldots, c_m$（$1 \leq c_i \leq n$），表示需要访问的部落编号。且$c_i$ 各不相同。

输出格式

• 如果两名翻译掌握的语言足以覆盖所有需要访问的部落，输出go go go（代表可以顺利出发）。
• 否则，输出dog dog dog（代表需要训练翻译），并在接下来的一行按升序输出所有需要额外学习的汪汪语编号。

样例

样例输入 1

8
65 170
3
1 2 3

样例输出 1

dog dog dog
3

样例输入 2

4
13 2
4
1 2 3 4

样例输出 2

go go go

数据范围与提示

• 所有输入均为整数。
• 部落编号从1到64。
• 翻译的语言能力用十进制数表示，范围为$0$到$2^n - 1$（对应n位二进制数）。
• 对于样例1，两名翻译的二进制表示分别为：
  • $a = 65 \rightarrow 0100\ 0001$（掌握第1和第7种汪汪语）
  • $b = 170 \rightarrow 1010\ 1010$（掌握第2、4、6、8种汪汪语）
  • 需要访问的部落为1、2、3，其中第3种汪汪语未被覆盖，因此需要额外学习。
• 对于样例2，两名翻译的二进制表示分别为：
  • $a = 13 \rightarrow 1101$（掌握第1、3、4种汪汪语）
  • $b = 2 \rightarrow 0010$（掌握第2种汪汪语）
  • 需要访问的部落为1、2、3、4，所有语言均被覆盖，因此无需额外学习。