27869번 - aFan Event Planning

SNS aFan은 매일 게시물을 게시할 때마다 최대 한 번 FANCO를 제공한다. FANCO는 블록체인으로 관리되는 암호화폐이며 aFan의 다양한 상품과 서비스를 구매하는 데 사용할 수 있다.

아인(AIN)이는 이번에 aFan에서 $N$일 동안 진행될 새로운 이벤트를 기획하고 있다. 이벤트 중 $i$번째 날에 글을 쓰면 FANCO와 함께 $E_i$개의 이벤트 토큰을 받을 수 있고, 받은 이벤트 토큰은 이벤트 기간 중에 열리는 이벤트 상점에서 사용할 수 있다.

이벤트가 진행되면서 이벤트 상점의 구성이 바뀔 수 있으며, 그때마다 사람들이 얻은 모든 이벤트 토큰은 모두 초기화되어 0개가 된다.

아인이는 앞으로 $Q$번의 테스트 동작을 해 보려고 한다. 동작에는 다음의 두 종류가 있다.

1. 이벤트의 $d$일차에서 $d+1$일차로 넘어가는 시점에 이벤트 상점의 구성을 바꾸기로 한다. 즉, $d+1$일차로 넘어가는 시점에 모든 이벤트 토큰이 초기화되도록 한다.
2. 이벤트 토큰을 하나도 가지고 있지 않던 어떤 사람이 이벤트의 $s$일차부터 $e$일차까지 매일 꾸준히 게시물을 작성했고, 그동안 이벤트 토큰을 전혀 소모하지 않았다고 하자. 이 사람이 $e$번째 날이 끝나기 직전에 가진 이벤트 토큰의 양을 구해 본다.

1번 종류의 동작은 이후의 동작에 계속해서 영향을 준다. 즉, 1번 종류의 동작을 추가로 한다고 해서 이전에 했던 1번 동작으로 만들어진 일정이 없어지지 않는다.

2번 종류의 동작이 주어질 때마다 예상되는 이벤트 토큰의 양을 구해 보자.

첫 번째 줄에 이벤트를 진행하는 날 수 $N$과 테스트 동작의 수 $Q$가 주어진다.

두 번째 줄에 이벤트 기간 중 각 날짜에 얻을 수 있는 이벤트 토큰의 수를 나타내는 $N$개의 정수 $E_1, E_2, \cdots, E_N$이 주어진다.

다음 $Q$개의 줄에는 테스트 동작이 처리해야 하는 순서대로 주어진다. 각 줄에 1번 종류의 동작은 $1\,d$의 형태로 주어지며, 2번 종류의 동작은 $2\,s\,e$의 형태로 주어진다. $d, s, e$는 모두 정수이다.

2번 종류의 테스트 동작이 주어질 때마다 각 줄에 예상되는 이벤트 토큰의 양을 출력한다.

• $1 \leq N, Q \leq 200\,000$
• $1 \leq E_i \leq 1\,000\,000\,000$
• $1 \leq d \lt N$
• 같은 $d$가 여러 번 주어지지 않는다.
• $1 \leq s \leq e \leq N$
• 마지막 동작은 반드시 2번 종류의 동작이다.