산맥

어떤 놀이공원에 새로운 롤러코스터 시뮬레이터가 설치되었다. 시뮬레이션 트랙은 $n$개의 레일이 끝과 끝을 맞대어 이어진 형태이며, 첫 번째 레일의 시작점은 높이 $0$에 고정되어 있다.

시뮬레이터는 트랙을 $n$개의 높이 변화량 $d_1, d_2, \dots, d_n$의 수열로 저장한다. $d_i$는 $i$번째 레일을 지나는 동안의 높이 변화량(cm)이다. 즉, 어떤 차량이 $i-1$개의 레일을 지난 뒤 높이 $e$에 있었다면, $i$번째 레일을 지난 뒤에는 높이 $e + d_i$에 있게 된다. 따라서 출발점의 높이는 $0$이고, $i$개의 레일을 지난 뒤의 높이는 $d_1 + d_2 + \dots + d_i$이다.

처음에는 모든 레일이 수평이다. 즉, 모든 $i$에 대해 $d_i = 0$이다.

하루 동안 다음 두 종류의 사건이 번갈아 발생한다.

• 재구성: 세 정수 $a$, $b$, $D$로 주어진다. $a \le i \le b$를 만족하는 모든 레일 $i$의 높이 변화량을 $d_i = D$로 설정한다. 다른 레일의 높이 변화량은 바뀌지 않는다. 시작점의 높이는 계속 $0$으로 유지되며, 이어지는 트랙 전체가 연결 상태를 유지하도록 필요한 만큼 위나 아래로 평행 이동한다.
• 탑승: 하나의 정수 $h$로 주어진다. 차량을 높이 $h$까지 도달할 수 있는 에너지로 출발시킨다. 차량은 트랙의 높이가 $h$를 넘지 않는 동안, 그리고 트랙의 끝에 도달하지 않은 동안 계속 나아간다.

각 탑승에 대해, 차량이 멈추기 전까지 완전히 지나간 레일의 개수를 구하여라.

첫째 줄에 레일의 개수 $n$이 주어진다 ($1 \le n \le 10^9$).

이후 여러 줄에 걸쳐 재구성과 탑승이 번갈아 주어지고, 마지막에 종료 표시가 주어진다. 각 줄은 다음 중 하나이다.

• 재구성: 문자 I와 세 정수 $a$, $b$, $D$가 공백 하나로 구분되어 주어진다 ($1 \le a \le b \le n$, $-10^9 \le D \le 10^9$). $a \le i \le b$인 모든 레일에 대해 $d_i = D$로 설정한다.
• 탑승: 문자 Q와 정수 $h$가 공백 하나로 구분되어 주어진다 ($0 \le h \le 10^9$).
• 문자 E 하나: 입력의 끝을 나타내는 종료 표시.

어느 순간에도 트랙 위 모든 지점의 높이는 구간 $[0, 10^9]$ cm 안에 있다고 가정해도 좋다. 입력은 최대 $100\,000$줄이다.

전체 테스트의 $50\%$에서는 $n$이 $1 \le n \le 20\,000$을 만족하며, 입력이 $1\,000$줄을 넘지 않는다.

각 탑승에 대해 한 줄씩, 차량이 지나간 레일의 개수를 정수 하나로 출력한다. $i$번째 줄에는 $i$번째 탑승의 결과를 출력한다.

각 재구성 전후의 트랙 모습이다. 가로축은 레일 번호를, 세로축과 점 위의 숫자는 높이를, 선분 위의 숫자는 높이 변화량을 나타낸다.