문제 준비

앤드루는 대회에 낼 프로그래밍 문제 $n$개를 만들었고, 이제 문제를 다듬으려고 한다. $i$번 문제를 준비하는 데 필요한 총 시간은 $t_i$분이라고 추정했다. 앤드루는 친구들을 불러 이 일을 나눠 맡길 생각이다.

몇 명이 도와줄지는 아직 모르지만 일은 공평하게 나누고 싶다. 그래서 $i$번 문제마다 정수 $x_i$를 정하고, 도와주는 친구는 모두 그 문제에 $x_i$분씩 쓴다. 친구들이 $i$번 문제에 쓴 시간의 합이 $t_i$분 이상이면 그 문제는 완전히 준비된 것이다. 친구가 $k$명일 때 $x_i$는 $k \times x_i \ge t_i$를 만족하는 가장 작은 정수로 정한다.

앤드루는 문제의 난이도를 잘못 봤다는 것을 알아차리면 $t_i$를 1 늘리거나 1 줄인다.

처음 추정한 $t_i$가 주어진다. 쿼리 $m$개를 주어진 순서대로 처리하라. 각 쿼리는 다음 중 하나다.

• 1 i: 앤드루가 $t_i$를 1 늘린다.
• 2 i: 앤드루가 $t_i$를 1 줄인다.
• 3 k: 친구 $k$명이 도와준다면 친구 한 명이 문제 $n$개를 준비하는 데 몇 분을 쓰는지 앤드루가 알고 싶어 한다.

첫째 줄에 문제의 개수 $n$과 쿼리의 개수 $m$이 주어진다. ($1 \le n, m \le 10^5$)

둘째 줄에 정수 $t_1, t_2, \dots, t_n$이 주어진다. $t_i$는 앤드루가 $i$번 문제에 대해 처음 추정한 시간이다. ($1 \le t_i \le 5 \times 10^5$)

다음 $m$개 줄에 쿼리가 한 줄에 하나씩, 두 정수 $q$와 $v$로 주어진다. $q$가 1이면 $t_v$를 1 늘리고, 2이면 $t_v$를 1 줄인다. 두 경우 모두 $1 \le v \le n$이다. $q$가 3이면 친구 $v$명이 도와줄 때 친구 한 명이 쓰는 시간을 구해야 한다. 이 경우 $1 \le v \le 5 \times 10^5$이다.

어떤 쿼리를 처리한 뒤에도 모든 $t_i$는 1 이상 $5 \times 10^5$ 이하다.

$q$가 3인 쿼리마다 친구 한 명이 문제 $n$개를 준비하는 데 쓰는 시간의 합 $x_1 + x_2 + \dots + x_n$을 한 줄에 하나씩 출력한다.