{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eVasya plays a popular game the Gnomes of Might and Magic.\u003c/p\u003e\u003cp\u003eIn this game Vasya manages the kingdom of gnomes, consisting of several castles, connected by bidirectional roads. The kingdom road network has a special form. The kingdom has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e main castles \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, which form the Good Path. This path consists of roads between the castles \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003ei\u003c/i\u003e \u0026lt; \u003ci\u003em\u003c/i\u003e)\u003c/span\u003e as well as the road between \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e. There are no other roads between the castles of the Good Path.\u003c/p\u003e\u003cp\u003eIn addition, for each pair of neighboring Good Path castles \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e there is exactly one Evil Shortcut — a path that goes along the roads leading from the first castle \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003eu\u003c/i\u003e)\u003c/span\u003e to the second one \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e and not having any common vertexes with the Good Path except for the vertexes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. It is known that there are no other roads and castles in the kingdom there, that is, every road and every castle lies either on the Good Path or the Evil Shortcut (castles can lie in both of them). In addition, no two Evil Shortcuts have any common castles, different than the castles of the Good Path.\u003c/p\u003e\u003cp\u003eAt the beginning of each week in the kingdom appears one very bad gnome who stands on one of the roads of the kingdom, and begins to rob the corovans going through this road. One road may accumulate multiple very bad gnomes. Vasya cares about his corovans, so sometimes he sends the Mission of Death from one castle to another.\u003c/p\u003e\u003cp\u003eLet\u0027s suggest that the Mission of Death should get from castle \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e to castle \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e. Then it will move from castle \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e to castle \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e, destroying all very bad gnomes, which are on the roads of the Mission\u0027s path. Vasya is so tough that his Mission of Death can destroy any number of gnomes on its way. However, Vasya is very kind, so he always chooses such path between castles \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e, following which he will destroy the smallest number of gnomes. If there are multiple such paths, then Vasya chooses the path that contains the smallest number of roads among them. If there are multiple such paths still, Vasya chooses the lexicographically minimal one among them.\u003c/p\u003e\u003cp\u003eHelp Vasya to simulate the life of the kingdom in the Gnomes of Might and Magic game.\u003c/p\u003e\u003cp\u003eA path is a sequence of castles, such that each pair of the neighboring castles on the path is connected by a road. Also, path \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ... , \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ep\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is lexicographically less than path \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ... , \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, if either \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e \u0026lt; \u003ci\u003eq\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e \u003d \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e \u003d \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ... , \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ep\u003c/i\u003e\u003c/sub\u003e \u003d \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ep\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, or exists such number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003er\u003c/i\u003e \u0026lt; \u003ci\u003ep\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e \u0026lt; \u003ci\u003eq\u003c/i\u003e)\u003c/span\u003e, that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e \u003d \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e \u003d \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ... , \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/sub\u003e \u003d \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003er\u003c/i\u003e + 1\u003c/sub\u003e \u0026lt; \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003er\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(3 ≤ \u003ci\u003em\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e ≤ 100000)\u003c/span\u003e — the number of castles in the kingdom, and the number of castles on the Good Path, respectively.\u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e integers, which are numbers of Good Path castles (the castles are numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e) in the order of occurrence on the Path, starting with some castle. All Good Path castles are different.\u003c/p\u003e\u003cp\u003eEach of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines describes an Evil Shortcut. First a line contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(3 ≤ \u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 100000)\u003c/span\u003e — the number of castles on the corresponding Evil Shortcut (with the two castles which are on the Good Path), followed by a \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e integers — number of castles in the order of occurrence in the given Shortcut. All castles in one Evil Shortcut are different. It is guaranteed that the first and the last castles from the Shortcut are on the Good Path and the first castles in the Evil Shortcuts form the Good Path and are presented in the same order in which the Path was represented on the second line.\u003c/p\u003e\u003cp\u003eThe next line contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 100000)\u003c/span\u003e — the number of events in the life of the kingdom. Each of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines describes a single event. An event is described by the symbol \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and two numbers or castles \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (the character and numbers of castles are separated by a single space). If the character of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is equal to \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e\" (a plus), it means that a very bad gnome (probably not the first one) has appeared on the road between castles \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. If \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e equals \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e\" (a question), then Vasya sent a Mission of Death from castle \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e to castle \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. It is guaranteed that for each request \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e\", the road between castles \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e exists. The events are given in chronological order, starting with the earliest one. Initially there are no very bad gnomes on the roads.\u003c/p\u003e\u003cp\u003eAll numbers in all lines are separated by single spaces. It is guaranteed that all the given Evil Shortcuts and Good Path fit in the limitations given in the problem statement.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each query \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e\" print a single number on a single line — the number of very bad gnomes destroyed by the corresponding Mission of Death. Print the answers to queries in the chronological order.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 3\n1 2 3\n3 1 4 2\n3 2 5 3\n3 3 6 1\n10\n+ 1 2\n+ 4 2\n+ 1 3\n+ 2 3\n? 1 2\n+ 2 5\n? 1 2\n? 1 2\n+ 1 2\n? 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n1\n0\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the example after the first four requests there is only one path from castle 1 to castle 2, which does not contain roads with very bad gnomes: 1 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/52b688473c12f0f165b3714bc138002e?v\u003d1716023672\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 6 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/52b688473c12f0f165b3714bc138002e?v\u003d1716023672\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 3 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/52b688473c12f0f165b3714bc138002e?v\u003d1716023672\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 5 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/52b688473c12f0f165b3714bc138002e?v\u003d1716023672\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 2.\u003c/p\u003e\u003cp\u003eAfter a gnome stood on the road (2, 5), the next Mission of Death moves along path 1 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/52b688473c12f0f165b3714bc138002e?v\u003d1716023672\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 2, and destroys the gnome, who was on the road (1, 2). The next Mission of Death follows the same path which is already free of gnomes.\u003c/p\u003e\u003cp\u003eAfter yet another gnome stood on the road (1, 2), the next Mission of Death goes on the path 1 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/52b688473c12f0f165b3714bc138002e?v\u003d1716023672\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 2, and kills the gnome.\u003c/p\u003e"}}]}