{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eTakahashi has many balls, on which nothing is written, and one bag.\r\nInitially, the bag is empty. Takahashi will do \u003cvar\u003e\\(Q\\)\u003c/var\u003e operations, each of which is of one of the following three types.\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eType \u003cvar\u003e\\(1\\)\u003c/var\u003e: Write an integer \u003cvar\u003e\\(X_i\\)\u003c/var\u003e on a blank ball and put it in the bag.\u003c/li\u003e\r\n\u003cli\u003eType \u003cvar\u003e\\(2\\)\u003c/var\u003e: For each ball in the bag, replace the integer written on it with that integer plus \u003cvar\u003e\\(X_i\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003cli\u003eType \u003cvar\u003e\\(3\\)\u003c/var\u003e: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eFor each \u003cvar\u003e\\(1\\leq i\\leq Q\\)\u003c/var\u003e, you are given the type \u003cvar\u003e\\(P_i\\)\u003c/var\u003e of the \u003cvar\u003e\\(i\\)\u003c/var\u003e-th operation and the value of \u003cvar\u003e\\(X_i\\)\u003c/var\u003e if the operation is of Type \u003cvar\u003e\\(1\\)\u003c/var\u003e or \u003cvar\u003e\\(2\\)\u003c/var\u003e. Print the integers recorded in the operations of Type \u003cvar\u003e\\(3\\)\u003c/var\u003e in order.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq Q \\leq 2\\times 10^5\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq P_i \\leq 3\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq X_i \\leq 10^9\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003eAll values in input are integers.\u003c/li\u003e\r\n\u003cli\u003eThere is one or more \u003cvar\u003e\\(i\\)\u003c/var\u003e such that \u003cvar\u003e\\(P_i\u003d3\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003cli\u003eIf \u003cvar\u003e\\(P_i\u003d3\\)\u003c/var\u003e, the bag contains at least one ball just before the \u003cvar\u003e\\(i\\)\u003c/var\u003e-th operation.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(Q\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(query_1\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(query_2\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(:\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(query_Q\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\u003cp\u003eEach \u003cvar\u003e\\(query_i\\)\u003c/var\u003e in the \u003cvar\u003e\\(2\\)\u003c/var\u003e-nd through \u003cvar\u003e\\((Q+1)\\)\u003c/var\u003e-th lines is in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(1\\)\u003c/var\u003e \u003cvar\u003e\\(X_i\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(2\\)\u003c/var\u003e \u003cvar\u003e\\(X_i\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(3\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\u003cp\u003eThe first number in each line is \u003cvar\u003e\\(1\\leq P_i\\leq 3\\)\u003c/var\u003e, representing the type of the operation.\r\nIf \u003cvar\u003e\\(P_i\u003d1\\)\u003c/var\u003e or \u003cvar\u003e\\(P_i\u003d2\\)\u003c/var\u003e, it is followed by a space, and then by \u003cvar\u003e\\(X_i\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eFor each operation with \u003cvar\u003e\\(P_i\u003d3\\)\u003c/var\u003e among the \u003cvar\u003e\\(Q\\)\u003c/var\u003e operations, print the recorded integer in its own line.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","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\r\n1 3\r\n1 5\r\n3\r\n2 2\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cp\u003eTakahashi will do the following operations.\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eWrite \u003cvar\u003e\\(3\\)\u003c/var\u003e on a ball and put it in the bag.\u003c/li\u003e\r\n\u003cli\u003eWrite \u003cvar\u003e\\(5\\)\u003c/var\u003e on a ball and put it in the bag.\u003c/li\u003e\r\n\u003cli\u003eThe bag now contains a ball with \u003cvar\u003e\\(3\\)\u003c/var\u003e and another with \u003cvar\u003e\\(5\\)\u003c/var\u003e. Pick up the ball with the smaller of them, or \u003cvar\u003e\\(3\\)\u003c/var\u003e. Record \u003cvar\u003e\\(3\\)\u003c/var\u003e and throw it away.\u003c/li\u003e\r\n\u003cli\u003eThe bag now contains just a ball with \u003cvar\u003e\\(5\\)\u003c/var\u003e. Replace this integer with \u003cvar\u003e\\(5+2\u003d7\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003cli\u003eThe bag now contains just a ball with \u003cvar\u003e\\(7\\)\u003c/var\u003e. Pick up this ball, record \u003cvar\u003e\\(7\\)\u003c/var\u003e, and throw it away.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eTherefore, we should print \u003cvar\u003e\\(3\\)\u003c/var\u003e and \u003cvar\u003e\\(7\\)\u003c/var\u003e, in the order they are recorded.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","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\r\n1 1000000000\r\n2 1000000000\r\n2 1000000000\r\n2 1000000000\r\n2 1000000000\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5000000000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cp\u003eNote that the outputs may not fit into a \u003cvar\u003e\\(32\\)\u003c/var\u003e-bit integer.\u003c/p\u003e\u003c/section\u003e\r\n"}}]}