{"raw_statement":[{"iden":"background","content":"JOISC2022 D3T3"},{"iden":"statement","content":"JOI 君是一个生物学家。他准备对蚂蚁和方糖做一些实验。\n\nJOI 君的实验在一个长度为 $10^9$ 的木条上进行。这根木条被从左往右放置。木条上距离左端点 $x$ 的点被称作坐标为 $x$ 的点。\n\n现在，木条上什么都没有。JOI 君将会进行 $Q$ 次操作。第 $i$ 个操作 $(1 \\le i \\le Q)$ 由三个整数 $T_i,X_i,A_i$ 描述，表示：\n\n- 若 $T_i=1$，JOI 君在坐标为 $X_i$ 的点处放了 $A_i$ 个蚂蚁。\n- 若 $T_i=2$，JOI 君在坐标为 $X_i$ 的点处放了 $A_i$ 块方糖。\n\n由于蚂蚁和方糖都很小，所以可能会有一些蚂蚁和方糖放在同一个点上。JOI 君也可能在同一个点执行多次操作。\n\n这次实验中使用的蚂蚁具有「好奇心强」的萌点。具体地，当 JOI 君拍手时，每个蚂蚁会执行以下操作：\n\n- 如果存在一块方糖与该蚂蚁距离不超过 $L$，它会选择任意一块并吃掉。\n\n可能存在多个蚂蚁同时吃掉一块方糖的情况。\n\n对于每个 $k$ $(1\\le k \\le Q)$，JOI 君想要知道以下问题的答案。\n\n- 假设 JOI 君在第 $k$ 次操作后拍了一次手，最多有多少块方糖被至少一个蚂蚁吃掉了？\n\n请写一个程序，对于给定的 JOI 君执行的操作和 $L$ 的值，对于所有 $k$ 回答 JOI 君的每个问题。\n\n注意 JOI 君并不会真的拍手。因此蚂蚁的位置不会改变，方糖也不会被吃掉。"},{"iden":"input","content":"第一行，两个正整数 $Q,L$，表示操作个数和蚂蚁可能吃到的方糖的范围。\n\n接下来 $Q$ 行，其中第 $i$ $(1 \\le i \\le Q)$ 包含三个整数 $T_i,X_i,A_i$，表示一次操作。"},{"iden":"output","content":"输出 $Q$ 行，第 $k$ $(1 \\le k \\le Q)$ 行包含一个整数，表示若 JOI 君在第 $k$ 次操作后拍了一次手，被至少一个蚂蚁吃掉的方糖的个数可能的最大值。"},{"iden":"note","content":"**【样例解释 #1】**\n\n在这组样例中，所有操作和每个 $k$ 的答案如下：\n\n 1. JOI 君在坐标为 $1$ 的点放了一个蚂蚁。  \n    由于没有方糖，对应的答案为 $0$。\n 2. JOI 君在坐标为 $2$ 的点放了一块方糖。  \n    假设 JOI 君此时拍手，则坐标为 $1$ 的蚂蚁会吃掉坐标为 $2$ 的方糖，所以对应的答案为 $1$。\n 3. JOI 君在坐标为 $3$ 的点放了一个蚂蚁。  \n    假设 JOI 君此时拍手，则坐标为 $1,3$ 的蚂蚁会同时吃掉坐标为 $2$ 的方糖，所以对应的答案为 $1$。\n 4. JOI 君在坐标为 $0$ 的点放了一块方糖。  \n    假设 JOI 君此时拍手，则坐标为 $1,3$ 的蚂蚁可以分别吃掉坐标为 $0,2$ 的方糖，所以对应的答案为 $2$。\n\n这组样例满足子任务 $1,2,4$ 的限制。\n\n**【样例解释 #2】**\n\n这组样例满足子任务 $1,2,4$ 的限制。\n\n**【样例解释 #3】**\n\n这组样例满足子任务 $1,4$ 的限制。\n\n**【样例解释 #4】**\n\n这组样例满足子任务 $1,3,4$ 的限制。\n\n**【数据范围】**\n\n对于所有数据，满足：\n\n- $1 \\le Q \\le 500\\,000$。\n- $1 \\le L \\le 10^9$。\n- $T_i \\in \\{1,2\\}$。\n- $0 \\le X_i \\le 10^9$ $(1 \\le i \\le Q)$。\n- $1 \\le A_i \\le 10^9$ $(1 \\le i \\le Q)$。\n\n详细子任务附加限制及分值如下表所示：\n\n|子任务编号|附加限制|分值|\n|:-:|:-:|:-:|\n|$1$|$Q \\le 3\\,000$|$6$|\n|$2$|$L=1$，$X_i \\le Q-1$，$X_i+T_i$ 是偶数 $(1\\le i\\le Q)$|$16$|\n|$3$|$Q$ 是偶数，$T_i = 1$ $(1 \\le i \\le Q/2)$，$T_i = 2$ $(Q/2+1 \\le i \\le Q)$|$26$|\n|$4$|无附加限制|$52$|"}],"translated_statement":null,"sample_group":[["4 1\n1 1 1\n2 2 1\n1 3 1\n2 0 1","0\n1\n1\n2"],["20 1\n2 16 778913911\n1 7 558407445\n1 1 589762439\n1 17 74646747\n1 1 149104909\n1 15 956697952\n2 6 389372991\n2 4 867453845\n1 15 157353445\n1 9 846177695\n1 7 747107163\n2 10 525670462\n2 16 478912944\n2 6 301733761\n2 12 132966485\n1 1 748012313\n2 10 830922632\n1 19 969484637\n1 13 370330582\n1 1 464798040","0\n0\n0\n74646747\n74646747\n778913911\n1168286902\n1168286902\n1168286902\n1168286902\n1168286902\n1693957364\n2103741597\n2405475358\n2405475358\n2405475358\n2725982591\n2725982591\n2858949076\n2858949076"],["20 6\n2 27 12\n2 9 11\n1 36 10\n2 39 4\n2 14 9\n2 33 7\n2 38 20\n2 0 20\n2 25 16\n1 14 3\n1 13 19\n2 6 4\n2 15 6\n2 33 4\n1 12 11\n1 44 1\n2 17 14\n2 12 19\n1 48 18\n2 30 16","0\n0\n0\n4\n4\n10\n10\n10\n10\n13\n30\n30\n32\n32\n40\n41\n44\n44\n44\n44"],["20 268886972\n1 984472666 733463744\n1 478477245 94817772\n1 242536956 330762563\n1 65794782 319137646\n1 320548477 937296140\n1 815011370 938193848\n1 565184190 917533785\n1 245417414 534089975\n1 529908772 977043962\n1 603891865 700935654\n2 167042244 479827216\n2 173921297 798343455\n2 916159596 810126726\n2 999299355 465535307\n2 965968070 501768990\n2 936073643 174976034\n2 832859952 778072072\n2 955489596 704853861\n2 246733786 382428992\n2 227669861 390905006","0\n0\n0\n0\n0\n0\n0\n0\n0\n0\n479827216\n1278170671\n2088297397\n2553832704\n2949828263\n2949828263\n3727900335\n3727900335\n4110329327\n4501234333"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}