#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e15;
// let stt[N, C, D, CC, CD, DC, DD]
struct state {
private:
inline static string lookup[7];
static string idx_to_string(int idx) { return lookup[idx]; }
static int idx_from_string(const string &s) {
auto it = find(lookup, lookup + 7, s);
assert(it != lookup + 7);
return it - lookup;
}
public:
inline static int to[7][7];
static void init() {
lookup[0] = "N", lookup[1] = "C", lookup[2] = "D", lookup[3] = "CC", lookup[4] = "CD", lookup[5] = "DC", lookup[6] = "DD";
for (int i = 0; i < 7; ++i) {
for (int j = 0; j < 7; ++j) {
if (i == 0) {
to[i][j] = j;
} else if (j == 0) {
to[i][j] = i;
} else {
string comb = idx_to_string(i) + idx_to_string(j);
if (idx_to_string(i).back() == idx_to_string(j).front()) {
to[i][j] = -1;
} else {
to[i][j] = idx_from_string(string(1, comb.front()) + string(1, comb.back()));
}
}
}
}
}
int64_t stt[7];
state() { // len>1 identity
for (int i = 0; i < 7; ++i) { stt[i] = 0; }
}
static state get(int64_t len) {
if (len != 1) {
return state();
}
return state(0, 0);
}
state(int64_t c, int64_t d) {
stt[0] = 0; // N
stt[1] = c; // C
stt[2] = d; // D
stt[3] = -inf; // CC
stt[4] = -inf; // CD
stt[5] = d + c; // DC
stt[6] = -inf; // DD
}
static state idt() {
state res;
for (int i = 0; i < 7; ++i) { res.stt[i] = -inf; }
return res;
}
bool operator==(const state &r) const = default;
};
state operator+(const state &l, const state &r) {
if (l == state::idt()) {
return r;
}
if (r == state::idt()) {
return l;
}
state res = state::idt();
for (int i = 0; i < 7; ++i) {
for (int j = 0; j < 7; ++j) {
int which = state::to[i][j];
if (which != -1) {
res.stt[which] = max(res.stt[which], l.stt[i] + r.stt[j]);
}
}
}
return res;
}
template <typename T>
class sparse_segment_tree {
struct node {
T cur;
int64_t lazy, lazy_c;
node *l, *r;
node(int64_t len) : l(nullptr), r(nullptr), lazy(0), lazy_c(0) {
if constexpr (is_same_v<T, state>) {
cur = T::get(len);
} else {
cur = T{};
}
}
~node() {
delete l;
delete r;
}
};
int64_t tl, tr;
node *t;
void push(node *t, int64_t tl, int64_t tr) {
// [N, C, D, CC, CD, DC, DD]
if constexpr (is_same_v<T, state>) {
static constexpr array<int, 7> m = {0, 1, -1, 1, 0, 0, -1};
static constexpr std::array<int, 7> m_c = {0, 1, 0, 2, 1, 1, 1};
for (int i = 0; i < 7; ++i) {
t->cur.stt[i] += m[i] * t->lazy;
t->cur.stt[i] += m_c[i] * t->lazy_c;
}
if (tl == tr) {
t->lazy = 0, t->lazy_c = 0;
return;
}
int64_t tm = midpoint(tl, tr);
t->l = t->l ? t->l : new node(tm - tl + 1);
t->r = t->r ? t->r : new node(tr - tm);
t->l->lazy += t->lazy, t->l->lazy_c += t->lazy_c;
t->r->lazy += t->lazy, t->r->lazy_c += t->lazy_c;
t->lazy = 0, t->lazy_c = 0;
}
}
void pull(node *t) {
t->cur = t->l->cur + t->r->cur;
}
void set(node *t, int64_t tl, int64_t tr, int64_t i, T st) {
push(t, tl, tr);
if (tr < i || i < tl) {
return;
}
if (tl == tr && tl == i) {
t->cur = st;
return;
}
int64_t tm = midpoint(tl, tr);
t->l = t->l ? t->l : new node(tm - tl + 1);
t->r = t->r ? t->r : new node(tr - tm);
set(t->l, tl, tm, i, st);
set(t->r, tm + 1, tr, i, st);
pull(t);
}
T query(node *t, int64_t tl, int64_t tr, int64_t l, int64_t r) {
push(t, tl, tr);
if (tr < l || r < tl) {
if constexpr (is_same_v<T, state>) {
return T::idt();
} else {
return T{};
}
}
if (l <= tl && tr <= r) {
return t->cur;
}
int64_t tm = midpoint(tl, tr);
t->l = t->l ? t->l : new node(tm - tl + 1);
t->r = t->r ? t->r : new node(tr - tm);
T res = query(t->l, tl, tm, l, r) + query(t->r, tm + 1, tr, l, r);
pull(t);
return res;
}
void add_same_suffix(node *t, int64_t tl, int64_t tr, int64_t l, int64_t x)
requires is_same_v<T, state>
{
push(t, tl, tr);
if (tr < l) {
return;
}
if (l <= tl) {
t->lazy += x;
push(t, tl, tr);
return;
}
int64_t tm = midpoint(tl, tr);
t->l = t->l ? t->l : new node(tm - tl + 1);
t->r = t->r ? t->r : new node(tr - tm);
add_same_suffix(t->l, tl, tm, l, x);
add_same_suffix(t->r, tm + 1, tr, l, x);
pull(t);
}
void add_range_c(node *t, int64_t tl, int64_t tr, int64_t l, int64_t r, int64_t x)
requires is_same_v<T, state>
{
push(t, tl, tr);
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
t->lazy_c += x;
push(t, tl, tr);
return;
}
int64_t tm = midpoint(tl, tr);
t->l = t->l ? t->l : new node(tm - tl + 1);
t->r = t->r ? t->r : new node(tr - tm);
add_range_c(t->l, tl, tm, l, r, x);
add_range_c(t->r, tm + 1, tr, l, r, x);
pull(t);
}
public:
sparse_segment_tree(int64_t tl, int64_t tr) : tl(tl), tr(tr), t(new node(tr - tl + 1)) {}
~sparse_segment_tree() { delete t; }
void set(int64_t i, T st) { set(t, tl, tr, i, st); }
T query(int64_t l, int64_t r) { return query(t, tl, tr, l, r); }
void add_same_suffix(int64_t l, int64_t x)
requires is_same_v<T, state>
{
add_same_suffix(t, tl, tr, l, x);
}
void add_range_c(int64_t l, int64_t r, int64_t x)
requires is_same_v<T, state>
{
add_range_c(t, tl, tr, l, r, x);
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
state::init();
// coordinate space extends from -1e9 to 2e9
// ants are a[]
// sugars are b[]
// operations: a[x] += val
// b[x] += val
// what is the maximum matching from a -> b?
// from a[i], there are edges to all of b[i-L], b[i-L+1], ..., b[i+L-1], b[i+L]
// so let's just choose intervals [li, ri] of a[] values (subsets <=> intervals)
// we must find the hall deficiency, that is:
//
// define cost(l,r) = sum(i=l to r) a[i] - sum(i=l-L to r+L) b[i]
//
// then max sum(cost(li, ri))
// let's simplify. define A(x) = sum(i=1 to x) a[i], B(x) = sum(i=1 to x) b[i]
// then cost(l,r) = (A(r) - A(l-1)) - (B(r+L) - B(l-L-1))
// = A(r)-B(r+L) - (A(l-1) - B(l-L-1))
//
// then, define c[x] = A(x)-B(x+L) and d[x] = B(x-L-1)-A(x-1), then
// cost(l,r) = c[r] + d[l]. Think of c[] and d[] as arrays.
// so as we span, we do
// [p1,p2] [p3,p4] ==> d[p1] + c[p2] + d[p3] + c[p4],
// which is DCDCDCDC
int q, L;
cin >> q >> L;
int64_t lo = -1e9 - 10, hi = 2e9 + 10;
sparse_segment_tree<int64_t> a(lo, hi), b(lo, hi);
sparse_segment_tree<state> st(lo + L + 1, hi - L);
// c[i] = A[i] - B[i+L]
// d[i] = B[i-L-1] - A[i-1]
// a[i] += x meaning =>
// A[idx] += x for all idx >= i
// meaning
// c[idx] += x for all idx >= i
// d[idx + 1] -= x for all idx >= i
// b[i] += x meaning =>
// c[idx] -= x for all idx >= i-L
// d[idx] += x for all idx >= i+L+1
auto compute = [&]() {
return st.query(lo + L + 1, hi - L).stt[5];
};
int64_t sum_ants = 0;
auto add_ants = [&](int x, int v) {
sum_ants += v;
a.set(x, a.query(x, x) + v);
st.add_range_c(x, x, v);
st.add_same_suffix(x + 1, v);
};
auto add_sugar = [&](int x, int v) {
b.set(x, b.query(x, x) + v);
st.add_same_suffix(x + L + 1, -v);
st.add_range_c(x - L, x + L, -v);
};
while (q--) {
int t, x, v;
cin >> t >> x >> v;
if (t == 1) {
add_ants(x, v);
} else {
add_sugar(x, v);
}
cout << min(sum_ants, sum_ants - compute()) << '\n';
}
}
