단층

먼 옛날 IOI 문명이 번성했지만 화산 분화로 멸망했다. 이 문명은 직선 모양의 하천을 따라 자리 잡았고, 멸망하던 시점의 지표면은 완전히 평평했다.

유적지를 좌표평면으로 보자. $x$축이 지표면이고 $y$축이 높이 방향이다. 직선 $y = 0$은 지표, 영역 $y > 0$은 지상, 영역 $y < 0$은 지하다. 문명이 멸망한 시점을 기준으로 $a$년 전($a \ge 0$)의 지층은 직선 $y = -a$ 위에 있었다.

문명이 멸망한 뒤 유적지에서 지각 변동이 $Q$번 일어났다. $i$번째 ($1 \le i \le Q$) 지각 변동은 위치 $X_i$, 방향 $D_i$, 변동량 $L_i$로 나타내고, $D_i$는 1 또는 2다. $i$번째 지각 변동은 다음 순서로 일어난다.

1. 지층이 이동한다.
   • $D_i = 1$이면 점 $(X_i, 0)$을 지나는 기울기 $1$의 직선을 따라 단층이 생기고, 이 직선보다 위쪽 영역에 있는 지층이 직선을 따라 높이 $L_i$만큼 이동한다. 즉 이 직선보다 위쪽에 있는 점 $(x, y)$는 점 $(x + L_i,\ y + L_i)$로 옮겨간다.
   • $D_i = 2$이면 점 $(X_i, 0)$을 지나는 기울기 $-1$의 직선을 따라 단층이 생기고, 이 직선보다 위쪽 영역에 있는 지층이 직선을 따라 높이 $L_i$만큼 이동한다. 즉 이 직선보다 위쪽에 있는 점 $(x, y)$는 점 $(x - L_i,\ y + L_i)$로 옮겨간다.
2. 이동한 직후 영역 $y > 0$에 놓인 지층은 풍화로 모두 사라진다.

시간이 흘러 현대에 고고학자 JOI 박사가 IOI 문명의 유적을 발굴한다. 박사는 그동안 일어난 지각 변동을 모두 알고 있고, 지금 지표에 드러난 지층이 문명 멸망 몇 년 전의 지층인지 알고 싶다.

지각 변동의 정보가 주어지면, $1 \le i \le N$인 각 정수 $i$에 대해 점 $(i - 1, 0)$과 점 $(i, 0)$ 사이의 지표에 드러난 지층이 문명 멸망 몇 년 전의 지층인지 구하라.

첫째 줄에 정수 $N$과 $Q$가 공백으로 구분되어 주어진다. 답을 구해야 하는 지층의 수가 $N$, 지각 변동의 수가 $Q$라는 뜻이다.

이어지는 $Q$개의 줄 중 $i$번째 줄 ($1 \le i \le Q$)에는 정수 $X_i$, $D_i$, $L_i$가 공백으로 구분되어 주어진다. $i$번째 지각 변동의 위치가 $X_i$, 방향이 $D_i$, 변동량이 $L_i$라는 뜻이다.

$N$개의 줄을 출력한다.

$i$번째 줄 ($1 \le i \le N$)에는 점 $(i - 1, 0)$과 점 $(i, 0)$ 사이의 지표에 드러난 지층이 문명 멸망 몇 년 전의 지층인지를 나타내는 정수 하나를 출력한다.

• $1 \le N \le 200000$
• $1 \le Q \le 200000$
• $-1000000000 \le X_i \le 1000000000$ ($1 \le i \le Q$)
• $1 \le D_i \le 2$ ($1 \le i \le Q$)
• $1 \le L_i \le 1000000000$ ($1 \le i \le Q$)