{"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\u003eIn this problem you will have to deal with a very special network.\u003c/p\u003e\u003cp\u003eThe network consists of two parts: part \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e and part \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e. Each part consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e vertices; \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th vertex of part \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e is denoted as \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\u003c/span\u003e, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th vertex of part \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e is denoted as \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eFor each index \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e \u0026lt; \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) there is a directed edge from vertex \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\u003c/span\u003e to vertex \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e, and from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e, respectively. Capacities of these edges are given in the input. Also there might be several directed edges going from part \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e to part \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e (but never from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eYou have to calculate the \u003ca href\u003d\"https://en.wikipedia.org/wiki/Maximum_flow_problem\"\u003emaximum flow value\u003c/a\u003e from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e in this network. Capacities of edges connecting \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\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e might sometimes change, and you also have to maintain the maximum flow value after these changes. Apart from that, the network is fixed (there are no changes in part \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e, no changes of edges going from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e, and no edge insertions or deletions).\u003c/p\u003e\u003cp\u003eTake a look at the example and the notes to understand the structure of the network better.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains three integer numbers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) — the number of vertices in each part, the number of edges going from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e and the number of changes, respectively.\u003c/p\u003e\u003cp\u003eThen \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e lines follow, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e denoting that the edge from \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\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e has capacity \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and the edge from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e has capacity \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\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\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThen \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines follow, describing the edges from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e. Each line contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e\u003c/span\u003e denoting an edge from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e with capacity \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ez\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e). There might be multiple edges from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eAnd then \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines follow, describing a sequence of changes to the network. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, denoting that the capacity of the edge from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/sub\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e + 1\u003c/sub\u003e\u003c/span\u003e is set to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\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\"\u003e1 ≤ \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFirstly, print the maximum flow value in the original network. Then print \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e integers, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of them must be equal to the maximum flow value after \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th change.\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\u003e4 3 2\n1 2\n3 4\n5 6\n2 2 7\n1 4 8\n4 3 9\n1 100\n2 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n14\n14\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\u003eThis is the original network in the example:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/98f52d98c6c1e9034ffbc42fd473d636?v\u003d1715605195\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}