{"raw_statement":[{"iden":"statement","content":"The world famous scientist Innokentiy continues his innovative experiments with decks of cards. Now he has a deck of n cards and k shuffle machines to shuffle this deck. As we know, i-th shuffle machine is characterized by its own numbers pi, 1, pi, 2, ..., pi, n such that if one puts n cards numbered in the order 1, 2, ..., n into the machine and presses the button on it, cards will be shuffled forming the deck pi, 1, pi, 2, ..., pi, n where numbers pi, 1, pi, 2, ..., pi, n are the same numbers of cards but rearranged in some order.\n\nAt the beginning of the experiment the cards in the deck are ordered as a1, a2, ..., an, i.e. the first position is occupied by the card with number a1, the second position — by the card with number a2, and so on. The scientist wants to transfer the card with number x to the first position. He can use all his shuffle machines as many times as he wants. You should determine if he can reach it.\n\nIn the first line the only positive integer n is written — the number of cards in the Innokentiy's deck.\n\nThe second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n) — the initial order of cards in the deck.\n\nThe third line contains the only positive integer k — the number of shuffle machines Innokentiy has.\n\nEach of the next k lines contains n distinct integers pi, 1, pi, 2, ..., pi, n (1 ≤ pi, j ≤ n) characterizing the corresponding shuffle machine.\n\nThe last line contains the only integer x (1 ≤ x ≤ n) — the number of card Innokentiy wants to transfer to the first position in the deck.\n\nNumbers n and k satisfy the condition 1 ≤ n·k ≤ 200000.\n\nOutput «_YES_» if the scientist can transfer the card with number x to the first position in the deck, and «_NO_» otherwise.\n\n"},{"iden":"input","content":"In the first line the only positive integer n is written — the number of cards in the Innokentiy's deck.The second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n) — the initial order of cards in the deck.The third line contains the only positive integer k — the number of shuffle machines Innokentiy has.Each of the next k lines contains n distinct integers pi, 1, pi, 2, ..., pi, n (1 ≤ pi, j ≤ n) characterizing the corresponding shuffle machine.The last line contains the only integer x (1 ≤ x ≤ n) — the number of card Innokentiy wants to transfer to the first position in the deck.Numbers n and k satisfy the condition 1 ≤ n·k ≤ 200000."},{"iden":"output","content":"Output «_YES_» if the scientist can transfer the card with number x to the first position in the deck, and «_NO_» otherwise."},{"iden":"examples","content":"Input44 3 2 121 2 4 32 3 1 41OutputYESInput44 3 2 121 2 4 32 1 3 41OutputNO"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cards.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\{1, \\dots, n\\}^n $ be the initial permutation of the deck.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of shuffle machines.  \nFor each $ i \\in \\{1, \\dots, k\\} $, let $ P_i = (p_{i,1}, p_{i,2}, \\dots, p_{i,n}) \\in S_n $ be a permutation representing the $ i $-th shuffle machine (i.e., applying $ P_i $ to a deck $ D = (d_1, \\dots, d_n) $ yields $ (d_{p_{i,1}}, d_{p_{i,2}}, \\dots, d_{p_{i,n}}) $).  \nLet $ x \\in \\{1, \\dots, n\\} $ be the target card number.\n\n**Constraints**  \n1. $ 1 \\leq n \\cdot k \\leq 200000 $  \n2. All $ a_i $ are distinct.  \n3. All $ p_{i,j} $ are distinct for each $ i $.\n\n**Objective**  \nDetermine whether there exists a finite sequence of applications of the permutations $ P_1, \\dots, P_k $ (in any order and any number of times) such that, when applied to the initial deck $ A $, the card $ x $ ends up in the first position.","simple_statement":"You have a deck of n cards with initial order a1, a2, ..., an.  \nYou have k shuffle machines. Each machine rearranges the deck in a fixed way.  \nYou can use any machine any number of times.  \nCan you move the card with number x to the first position?","has_page_source":false}