{"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\u003eThere are $$$n$$$ students and $$$m$$$ clubs in a college. The clubs are numbered from $$$1$$$ to $$$m$$$. Each student has a potential $$$p_i$$$ and is a member of the club with index $$$c_i$$$. Initially, each student is a member of exactly one club. A technical fest starts in the college, and it will run for the next $$$d$$$ days. There is a coding competition every day in the technical fest. \u003c/p\u003e\u003cp\u003eEvery day, in the morning, exactly one student of the college leaves their club. Once a student leaves their club, they will never join any club again. Every day, in the afternoon, the director of the college will select one student from each club (in case some club has no members, nobody is selected from that club) to form a team for this day\u0027s coding competition. The strength of a team is the mex of potentials of the students in the team. The director wants to know the maximum possible strength of the team for each of the coming $$$d$$$ days. Thus, every day the director chooses such team, that the team strength is maximized.\u003c/p\u003e\u003cp\u003eThe \u003cspan class\u003d\"tex-font-style-it\"\u003emex\u003c/span\u003e of the multiset $$$S$$$ is the smallest non-negative integer that is not present in $$$S$$$. For example, the mex of the $$$\\{0, 1, 1, 2, 4, 5, 9\\}$$$ is $$$3$$$, the mex of $$$\\{1, 2, 3\\}$$$ is $$$0$$$ and the mex of $$$\\varnothing$$$ (empty set) is $$$0$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \\leq m \\leq n \\leq 5000$$$), the number of students and the number of clubs in college.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ integers $$$p_1, p_2, \\ldots, p_n$$$ ($$$0 \\leq p_i \u0026lt; 5000$$$), where $$$p_i$$$ is the potential of the $$$i$$$-th student.\u003c/p\u003e\u003cp\u003eThe third line contains $$$n$$$ integers $$$c_1, c_2, \\ldots, c_n$$$ ($$$1 \\leq c_i \\leq m$$$), which means that $$$i$$$-th student is initially a member of the club with index $$$c_i$$$.\u003c/p\u003e\u003cp\u003eThe fourth line contains an integer $$$d$$$ ($$$1 \\leq d \\leq n$$$), number of days for which the director wants to know the maximum possible strength of the team. \u003c/p\u003e\u003cp\u003eEach of the next $$$d$$$ lines contains an integer $$$k_i$$$ ($$$1 \\leq k_i \\leq n$$$), which means that $$$k_i$$$-th student lefts their club on the $$$i$$$-th day. It is guaranteed, that the $$$k_i$$$-th student has not left their club earlier.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each of the $$$d$$$ days, print the maximum possible strength of the team on that day.\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\u003e5 3\n0 1 2 2 0\n1 2 2 3 2\n5\n3\n2\n4\n5\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1\n1\n1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e5 3\n0 1 2 2 1\n1 3 2 3 2\n5\n4\n2\n3\n5\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n2\n1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e5 5\n0 1 2 4 5\n1 2 3 4 5\n4\n2\n3\n5\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n1\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\u003eConsider the first example:\u003c/p\u003e\u003cp\u003eOn the first day, student $$$3$$$ leaves their club. Now, the remaining students are $$$1$$$, $$$2$$$, $$$4$$$ and $$$5$$$. We can select students $$$1$$$, $$$2$$$ and $$$4$$$ to get maximum possible strength, which is $$$3$$$. Note, that we can\u0027t select students $$$1$$$, $$$2$$$ and $$$5$$$, as students $$$2$$$ and $$$5$$$ belong to the same club. Also, we can\u0027t select students $$$1$$$, $$$3$$$ and $$$4$$$, since student $$$3$$$ has left their club.\u003c/p\u003e\u003cp\u003eOn the second day, student $$$2$$$ leaves their club. Now, the remaining students are $$$1$$$, $$$4$$$ and $$$5$$$. We can select students $$$1$$$, $$$4$$$ and $$$5$$$ to get maximum possible strength, which is $$$1$$$.\u003c/p\u003e\u003cp\u003eOn the third day, the remaining students are $$$1$$$ and $$$5$$$. We can select students $$$1$$$ and $$$5$$$ to get maximum possible strength, which is $$$1$$$.\u003c/p\u003e\u003cp\u003eOn the fourth day, the remaining student is $$$1$$$. We can select student $$$1$$$ to get maximum possible strength, which is $$$1$$$. \u003c/p\u003e\u003cp\u003eOn the fifth day, no club has students and so the maximum possible strength is $$$0$$$.\u003c/p\u003e"}}]}