题目内容

体育课把学员排成一列，做追逐与护挡。列里每个人有一个互不相同的代号，站位不按代号大小。

追逐者每轮指向当前列中的某一站，护挡者同一轮也指向一站。两人都按从左往右第 $1$ 站起算。

指向落在同一站时，这一轮扑空，没有人离列。两站不同，而且追逐者的站号仍在当前人数之内，则该站学员离列，其右侧的人依次左移，列中不留空档。追逐者的站号小于 $1$ 或大于当前人数时，这一轮没有人离列。护挡者的站号小于 $1$ 或大于当前人数时，护挡不算数；只要追逐者的站号仍然有效，该站学员仍要离列。

某一轮结束后，列上人数小于等于 $1$，练习立刻失败，后面的轮次不再进行。全部轮次做完后人数仍大于 $1$，练习成功。

输入描述

第一行一个整数 $p$，表示一开始的人数。

第二行 $p$ 个整数 $s_1,s_2,\dots,s_p$，从左到右是每个人的代号。

第三行一个整数 $r$，表示轮数。

接下来 $r$ 行，每行两个整数 $g$ 和 $h$。$g$ 是护挡者指向的站号，$h$ 是追逐者指向的站号。

$2 \le p \le 1000$，$1 \le r \le 1000$。

代号互不相同，且 $-10^9 \le s_k \le 10^9$。$g$ 与 $h$ 为整数，$-10^9 \le g,h \le 10^9$。

输出描述

输出两行。

第一行是结果：$bai$ 表示失败，$sheng$ 表示成功。

第二行是仍留在列上的代号，相邻两个之间用一个空格隔开。失败时按当时从左到右的顺序书写。成功时按代号从小到大书写。

样例1

输入

5
8 3 6 1 9
4
4 2
1 1
2 5
1 3

输出

sheng
6 8 9

说明

开始一列是 $8\ 3\ 6\ 1\ 9$。

第 $1$ 轮护挡指向 $4$、追逐指向 $2$，两站不同，第 $2$ 站的 $3$ 离列，剩下 $8\ 6\ 1\ 9$。

第 $2$ 轮两人都指向 $1$，扑空，队列不变。

第 $3$ 轮追逐指向 $5$，当前只有 $4$ 人，没有人离列。

第 $4$ 轮护挡指向 $1$、追逐指向 $3$，第 $3$ 站的 $1$ 离列，剩下 $8\ 6\ 9$。人数仍大于 $1$，成功。代号从小到大是 $6\ 8\ 9$。

样例2

输入

3
4 9 2
2
1 3
2 1

输出

bai
9

说明

开始是 $4\ 9\ 2$。第 $1$ 轮追逐指向 $3$，护挡指向 $1$，代号 $2$ 离列，剩下 $4\ 9$。第 $2$ 轮追逐指向 $1$，护挡指向 $2$，代号 $4$ 离列，只剩 $9$。人数已经不超过 $1$，失败，后面即使还有轮次也不再进行。