#pragma GCC optimize("Ofast,unroll-all-loops")
#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);
}
};
struct query {
int t, x, v;
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
state::init();
vector<int64_t> buff;
int q, L;
cin >> q >> L;
vector<query> queries(q);
for (auto &[t, x, v] : queries) {
cin >> t >> x >> v;
buff.push_back(x);
buff.push_back(x + 1);
buff.push_back(x + L + 1);
buff.push_back(x - L);
buff.push_back(x + L);
}
int64_t lo = -1e9 - 10, hi = 2e9 + 10;
buff.push_back(lo + L + 1), buff.push_back(hi - L);
sort(buff.begin(), buff.end());
buff.erase(unique(buff.begin(), buff.end()), buff.end());
auto C = [&](int64_t x) { return lower_bound(buff.begin(), buff.end(), x) - buff.begin(); };
sparse_segment_tree<state> st(C(lo + L + 1), C(hi - L));
auto compute = [&]() {
return st.query(C(lo + L + 1), C(hi - L)).stt[5];
};
int64_t sum_ants = 0;
auto add_ants = [&](int x, int v) {
sum_ants += v;
st.add_range_c(C(x), C(x), v);
st.add_same_suffix(C(x + 1), v);
};
auto add_sugar = [&](int x, int v) {
st.add_same_suffix(C(x + L + 1), -v);
st.add_range_c(C(x - L), C(x + L), -v);
};
for (auto &[t, x, v] : queries) {
if (t == 1) {
add_ants(x, v);
} else {
add_sugar(x, v);
}
cout << min(sum_ants, sum_ants - compute()) << '\n';
}
}
