먼 옛날, IOI 문명이라는 고도의 문명이 번성하였다. 그러나 화산 폭발로 인해 이 문명은 멸망하고 말았다. IOI 문명은 직선 형태의 강을 따라 번영하였으며, 멸망 당시 그 표면은 평평하였다. IOI 문명의 유적지는 좌표 평면의 x축으로 간주할 수 있다. y축은 높이 방향을 나타낸다. 즉, 좌표 평면에서 직선 y = 0은 지표를, y > 0은 지상, y < 0은 지하를 나타낸다. 또한, IOI 문명이 멸망했을 때, a년 전(a ≧ 0)의 지층은 직선 y = −a의 위치에 있었다.

IOI 문명이 멸망한 이후, 이 유적지에서는 Q번의 지각 변동이 일어났다. i번째 지각 변동(1 ≦ i ≦ Q)은 위치 Xi, 방향 Di, 변동량 Li로 나타낼 수 있다. Di는 1 또는 2이다. i번째 지각 변동은 다음 두 단계로 일어난다.

1. 지층이 다음과 같이 이동한다.

Di = 1일 경우, 단층이 점 (Xi, 0)을 지나는 기울기 1의 직선에 따라 형성되며, 이 직선보다 위쪽에 있는 지층이 직선을 따라 높이 Li만큼 이동한다. 즉, 이 직선보다 위쪽에 있는 점 (x, y)는 점 (x + Li, y + Li)로 이동한다.
Di = 2일 경우, 단층이 점 (Xi, 0)을 지나는 기울기 −1의 직선에 따라 형성되며, 이 직선보다 위쪽에 있는 지층이 직선을 따라 높이 Li만큼 이동한다. 즉, 이 직선보다 위쪽에 있는 점 (x, y)는 점 (x − Li, y + Li)로 이동한다.

2. 직후, y > 0의 영역에 있는 지층은 풍화로 인해 모두 사라진다.

시대가 흘러 현대에, 고고학자인 JOI 박사는 IOI 문명의 유적을 발굴하기로 하였다. JOI 박사는 어느 위치의 지표 지층이 IOI 문명이 멸망하기 몇 년 전의 지층인지 알고 싶어 한다. 어떤 지각 변동이 일어났는지는 알고 있다. 당신의 임무는 JOI 박사를 대신하여 1 ≦ i ≦ N을 만족하는 각 정수 i에 대해, 점 (i − 1, 0)과 점 (i, 0) 사이의 지표 지층이 IOI 문명이 멸망하기 몇 년 전의 지층인지 구하는 것이다.

#8202 upload 9 done 5 how_to_reg 4 call_split Subtask

단층 timer 2s memory 256MB

#8202
Subtask

단층 2s 256MB