살균 스프레이

JOI 씨는 IOI 제약 회사에서 일하고 있다. 이 회사에서는 연구원들이 새로운 살균 스프레이를 개발하기 위한 실험 작업으로 바쁘다.

이 회사에서 살균 스프레이의 강도는 다음과 같이 정의된다. 세균이 y마리 있는 배양 접시에 강도 x의 스프레이를 한 번 사용하면, 그 배양 접시의 세균 수는 ⌊y/x⌋, 즉 y/x에서 소수 부분을 버린 정수가 된다. 이제 강도 K인 새 스프레이가 개발되었다. 이 스프레이의 성능을 시험하기 위해 실험을 진행하려고 한다. 번호가 1, ..., N인 배양 접시 N개를 사용한다. 처음에 배양 접시 i에는 세균이 Ci마리 있다. 실험에서는 Q개의 연산을 순서대로 수행한다. 각 연산은 다음 중 하나이다.

• 연산 1: 배양 접시 a와 정수 b를 선택하여 배양 접시 a의 세균 수를 조정한다. 이 연산 후 배양 접시 a의 세균 수는 b가 된다.
• 연산 2: 1 ≤ l ≤ r ≤ N인 두 정수 l, r을 선택한다. 배양 접시 l, l + 1, ..., r - 1, r 각각에 스프레이를 한 번씩 뿌린다.
• 연산 3: 1 ≤ l ≤ r ≤ N인 두 정수 l, r을 선택한다. 배양 접시 l, l + 1, ..., r - 1, r의 세균 수 합을 계산하여 기록한다.

JOI 씨는 새 스프레이가 예상대로 작동한다고 가정할 때 실험 결과가 궁금하다. 훌륭한 프로그래머인 당신에게 실험 결과를 예측해 달라고 부탁한다.

실험에서 연산 3들에 의해 기록되는 수를 구하는 프로그램을 작성하시오.

스프레이의 강도와 실험의 연산 정보가 주어졌을 때, 연산 3들에 의해 기록되는 수를 구하는 프로그램을 작성하시오.

표준 입력에서 다음 데이터를 읽는다.

• 입력의 첫째 줄에는 공백으로 구분된 세 정수 N, Q, K가 주어진다. 이는 스프레이의 강도가 K이고, 배양 접시의 수가 N이며, 실험의 연산 수가 Q라는 뜻이다.

• 다음 N개 줄의 i번째 줄(1 ≤ i ≤ N)에는 정수 Ci가 주어진다. 이는 실험 시작 시 배양 접시 i에 세균이 Ci마리 있다는 뜻이다.

• 다음 Q개 줄의 i번째 줄(1 ≤ i ≤ Q)에는 공백으로 구분된 세 정수 Si, Ti, Ui가 주어진다. 이는 실험의 i번째 연산 정보를 나타낸다.

  • Si = 1일 때, a = Ti, b = Ui인 연산 1을 뜻한다.
  • Si = 2일 때, l = Ti, r = Ui인 연산 2를 뜻한다.
  • Si = 3일 때, l = Ti, r = Ui인 연산 3을 뜻한다.

실험에서 연산 3들에 의해 기록되는 수를 출력한다. 출력하는 줄의 수는 실험에서 수행된 연산 3의 수와 같다.

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 100 000.
• 1 ≤ Q ≤ 100 000.
• 1 ≤ K ≤ 10.
• 0 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ N).
• 1 ≤ Si ≤ 3 (1 ≤ i ≤ Q).
• Si = 1일 때, 1 ≤ Ti ≤ N이고 0 ≤ Ui ≤ 1 000 000 000 (1 ≤ i ≤ Q).
• Si = 2, 3일 때, 1 ≤ Ti ≤ Ui ≤ N (1 ≤ i ≤ Q).