{"raw_statement":[{"iden":"problem statement","content":"> The problem setting of this problem is partially shared with Problem A.\n\nIn the year $3333$, CatCoder will hold the CatCoder Triple Contest (abbreviated as C3C).\nThere are $N$ writers who have problem proposals. Each writer's problem proposals are classified into $5$ types by difficulty: Hell, Hard, Medium, Easy, Baby, and the $i$\\-th writer has $A_i,B_i,C_i,D_i,E_i$ problem proposals of Hell, Hard, Medium, Easy, Baby, respectively.\nEach C3C simultaneously holds $3$ divisions, Div.1, Div.2, and Div.3. The problem proposals required for each division are as follows:\n\n*   Div.1: One Hell, one Hard, and one Medium problem proposal from the same writer\n*   Div.2: One Hard, one Medium, and one Easy problem proposal from the same writer\n*   Div.3: One Medium, one Easy, and one Baby problem proposal from the same writer\n\nNote that **the writers for Div.1, Div.2, and Div.3 do not necessarily have to be the same**. Also, each problem proposal can be used in at most one division of one C3C.\nFor $k=1,2,\\dots,N$, let $X_k$ be the maximum number of times C3C can be held using only the problem proposals of the first $k$ writers. Find $X_1,X_2,\\dots ,X_N$.\n$T$ test cases are given, so find the answer for each."},{"iden":"constraints","content":"*   $1 \\le T \\le 10^5$\n*   $1 \\le N \\le 2 \\times 10^5$\n*   $1 \\le A_i,B_i,C_i,D_i,E_i \\le 10^9$\n*   The sum of $N$ over all test cases is at most $2 \\times 10^5$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_1$ $B_1$ $C_1$ $D_1$ $E_1$\n$A_2$ $B_2$ $C_2$ $D_2$ $E_2$\n$\\vdots$\n$A_N$ $B_N$ $C_N$ $D_N$ $E_N$"},{"iden":"sample input 1","content":"3\n2\n3 3 3 3 3\n3 1 4 2 5\n7\n1000000000 1000000000 1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000 1000000000 1000000000\n10\n145852338 455046273 447701888 302317605 187706517\n469056787 117990013 461926296 216907828 419205454\n89931495 63942616 324197994 555154220 469433755\n285221794 487750820 398191999 232324766 44467392\n356205020 422423283 451558541 314957395 11846473\n212753197 384933474 328150388 111956686 11132031\n414426705 377305504 500797865 354689082 115544977\n176361367 59266253 439600074 328676554 233005233\n310994713 74852265 430187235 889232556 487055975\n22464564 297489263 186185204 29275688 641606972"},{"iden":"sample output 1","content":"1 2\n333333333 666666666 1000000000 1333333333 1666666666 2000000000 2333333333\n145852338 259612716 314817258 501663240 646419826 751331137 911803212 1016363776 1143191852 1169061978\n\nFor the first test case, for example when $k=2$, C3C can be held $2$ times by using problem proposals as follows:\n\nDiv.1\n\nDiv.2\n\nDiv.3\n\n$1$st time\n\nHell, Hard, Medium from the $1$st writer\n\nHard, Medium, Easy from the $1$st writer\n\nMedium, Easy, Baby from the $2$nd writer\n\n$2$nd time\n\nHell, Hard, Medium from the $2$nd writer\n\nHard, Medium, Easy from the $1$st writer\n\nMedium, Easy, Baby from the $2$nd writer"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}