[POI2010] TES-Intelligence Test

题目描述

One of the tasks in the Byteotian Intelligence Test (BIT) is to cross out numbers from an initial sequence in such a way that leaves as a result certain given sequences. Byteasar longs to become the IQ Master of Byteotia, but he is no good in this kind of tasks. But since practice makes perfect, he intends to practise a lot. So much in fact that he asks you to write a program that will facilitate the training by verifying his answers quickly. Byteotian智力测试机构的一项工作就是按照一定的规则删除一个序列的数字,得到一个确定的数列。Byteasar很渴望成为Byteotian智力测试机构的主管,但是他在这个工作上做的并不好,俗话说熟能生巧,他打算做很多练习,所以他希望你写一个程序来快速判断他的答案是否正确。

输入输出格式

输入格式


The first line of the standard input contains one integer $m$ ($1\le m\le 1\ 000\ 000$). The second line holds $m$ integers $a_1,a_2,\cdots,a_m$ ($1\le a_i\le 1\ 000\ 000$ for $1\le i\le m$), separated by single spaces, that constitute the initial sequence of the test. The third line of the input holds one integer $n$. The following $2n$ lines describe the sequences to be obtained by crossing out numbers from the initial sequence. Each sequence's description takes two successive lines. The first of these two lines contains an integer $m_i$ ($1\le m_i\le 1\ 000\ 000$). The second contains an $m_i$-element long sequence of integers $b_{i,1},b_{i,2},\cdots,b_{i,m_i}$($1\le b_{i,j}\le 1\ 000\ 000$ for $1\le j\le m_i$)separated by single spaces. You may assume that the total length on given $n$ sequences does not exceed $1\ 000\ 000$. 第一行为一个整数m(1<=m<=1000000)第二行包括m个用空格分开的整数ai(1<=ai<=1000000),组成了最初的序列,第三行为一个整数n(1<=n<=1000000),表示n个Byteasar经过一系列删除得到的序列,每个序列两行,第一行给出长度L(1<=L<=m),然后下一行为L个由空格分开的整数bi(1<=bi<=1000000)。

输出格式


Your program should print out $n$ lines to the standard output. The $i$-th line (for $1\le i\le n$) should hold one word, "TAK" (yes in Polish) if the $i$-th input sequence can be obtained by crossing out (i.e., removing) some, not necessarily contiguous, numbers from the initial sequence, or "NIE" (no in Polish) otherwise. Mind you, only the words should be printed, no quotation marks. Of course, the order of the numbers left after crossing out is important, as can be seen in the example. 共n行,如果Byteasar的序列确实是由最初的序列删除一些数得到,就输出TAK,否则输出NIE。

输入输出样例

输入样例 #1

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

输出样例 #1

TAK
NIE
TAK
NIE

说明

题目简述:给定一个数串,和m个小数串,问这些小串都是不是大数字串的子序列 感谢@Yhy9630 提供翻译