{"raw_statement":[{"iden":"statement","content":"King Triton really likes watching sport competitions on TV. But much more Triton likes watching live competitions. So Triton decides to set up a swimming competition in the kingdom Merfolk. Thousands of creatures come to take part in competition, that's why it is too difficult to take the first place.\n\nFor the King's beloved daughter Ariel this competition is the first in her life. Ariel is very kind, so she wants to give a lot of gold medals. Ariel says, that it is unfair to make a single ranking list for creatures that are so different. It is really a good result to be the fastest small fish without tail in Merfolk!\n\nAriel chooses k important traits (such as size, tailness, rapacity and so on). A creature can either possess a trait or not (there are no intermediate options).\n\nA score is given for each creature (it doesn't matter how it was calculated) and the list of possessed traits f1, ..., fy is also given.\n\nAriel wants to know the place occupied by creature a in a competition among creatures, who have the same traits h1, ..., ht. So if creature a doesn't have a trait hi, then all creatures in the competition are without this trait. If creature a has a trait hi, then all creatures in the competition have this trait. Other traits doesn't matter. The winner of the competition is a creature with the maximum score.\n\nThe first line contains n (1 ≤ n ≤ 104) and k (1 ≤ k ≤ 10). The next n lines contain information about creatures: score (1 ≤ score ≤ 109), y (0 ≤ y ≤ k) — the number of possessed traits, and y numbers fi (1 ≤ fi ≤ k) — ids of possessed traits. All fi in one line are different.\n\nThe next line contains m (1 ≤ m ≤ 105) — the number of queries from Ariel. The next m lines describe queries: a (1 ≤ a ≤ n) — the id of a creature, then t — the number of traits, then t numbers hi. All hi in one line are different.\n\nFor each query output the place of a creature a in ranking list amount the corresponded creatures. If several creatures have the same score all of them take the same place.\n\n"},{"iden":"input","content":"The first line contains n (1 ≤ n ≤ 104) and k (1 ≤ k ≤ 10). The next n lines contain information about creatures: score (1 ≤ score ≤ 109), y (0 ≤ y ≤ k) — the number of possessed traits, and y numbers fi (1 ≤ fi ≤ k) — ids of possessed traits. All fi in one line are different.The next line contains m (1 ≤ m ≤ 105) — the number of queries from Ariel. The next m lines describe queries: a (1 ≤ a ≤ n) — the id of a creature, then t — the number of traits, then t numbers hi. All hi in one line are different."},{"iden":"output","content":"For each query output the place of a creature a in ranking list amount the corresponded creatures. If several creatures have the same score all of them take the same place."},{"iden":"examples","content":"Input3 2100 1 150 1 230 2 1 2121 2 1 21 1 11 1 21 02 02 1 12 1 22 2 2 13 03 2 1 23 1 23 1 1Output111121113122Input3 2100 010 0100 031 02 03 0Output131"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of creatures, $ k \\in \\mathbb{Z}^+ $ the number of possible traits.  \nEach creature $ i \\in \\{1, \\dots, n\\} $ has:  \n- A score $ s_i \\in \\mathbb{Z}^+ $,  \n- A trait set $ T_i \\subseteq \\{1, \\dots, k\\} $, where $ |T_i| \\leq k $.  \n\nLet $ m \\in \\mathbb{Z}^+ $ be the number of queries.  \nEach query $ q \\in \\{1, \\dots, m\\} $ is specified by:  \n- A creature index $ a_q \\in \\{1, \\dots, n\\} $,  \n- A subset of traits $ H_q = \\{h_1, \\dots, h_{t_q}\\} \\subseteq \\{1, \\dots, k\\} $, $ t_q \\geq 0 $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^4 $, $ 1 \\leq k \\leq 10 $  \n2. $ 1 \\leq s_i \\leq 10^9 $  \n3. $ 0 \\leq |T_i| \\leq k $  \n4. $ 1 \\leq m \\leq 10^5 $  \n5. For each query: $ 1 \\leq a_q \\leq n $, $ 0 \\leq t_q \\leq k $, $ h_j \\in \\{1, \\dots, k\\} $, all distinct.  \n\n**Objective**  \nFor each query $ q $:  \nDefine the subset of creatures:  \n$$\nC_q = \\left\\{ i \\in \\{1, \\dots, n\\} \\mid T_i \\cap H_q = T_{a_q} \\cap H_q \\right\\}\n$$  \nThat is, creature $ i $ is in $ C_q $ iff it agrees with creature $ a_q $ on all traits in $ H_q $:  \n- If $ h \\in H_q \\cap T_{a_q} $, then $ h \\in T_i $,  \n- If $ h \\in H_q \\setminus T_{a_q} $, then $ h \\notin T_i $.  \n\nLet $ S_q = \\{ s_i \\mid i \\in C_q \\} $.  \nLet $ r_q $ be the rank (place) of creature $ a_q $ in $ C_q $, defined as:  \n$$\nr_q = 1 + \\left| \\left\\{ i \\in C_q \\mid s_i > s_{a_q} \\right\\} \\right|\n$$  \nOutput $ r_q $.","simple_statement":"Given n creatures, each with a score and a set of traits (from k possible traits), and m queries: for each query, find the rank of a specific creature among all creatures that share exactly the same specified traits (ignore other traits). Rank is based on score (highest score = rank 1), and equal scores get the same rank.","has_page_source":false}