34039번 - 마이마이 순회 돌기

문제

승민이는 리듬 게임 마이마이에 푹 빠져 있다. 게임을 하는 데 사용할 수 있는 시간이 적은 승민이는 주어진 시간 내에 최대한 많은 곡을 클리어하고자 한다. 마이마이에는 현재 총 $N$개의 곡이 수록되어 있으며, 곡마다 클리어에 필요한 시간이 정해져 있다. 또한, 곡의 클리어 시간이 바뀌거나 신곡이 추가될 수 있으므로, 다음 세 종류의 쿼리를 처리해야 한다:

• 1ドル$ $j$ $v$: $j$번째 곡을 클리어하는 데 필요한 소요 시간을 $v$ 로 변경한다.
• 2ドル$ $T$: 게임을 하는 데 사용할 수 있는 시간이 $T$일 때, 클리어할 수 있는 곡의 최대 개수를 출력한다. 클리어 시간 이외의 시간은 무시한다.
• 3ドル$ $v$: 소요 시간이 $v$인 신곡을 리스트의 맨 뒤에 추가한다. 만일 지금 수록곡이 $M$개라면, 신곡의 곡 번호는 $M+1$이 된다.

승민이는 같은 곡을 반복해서 클리어하는 것을 싫어하기 때문에, 한 쿼리 내에서는 서로 다른 곡만 선택할 수 있다. 이때, 다음에 선택하는 곡의 인덱스가 연속되어 있을 필요는 없다.

각 쿼리는 독립적으로 판단되므로, 이전 쿼리에서 사용한 곡도 이후 쿼리에서 다시 선택할 수 있다.

입력

첫째 줄에 정수 $N$과 $Q$가 공백으로 구분되어 주어진다.

둘째 줄에 $N$개의 정수 $a_1,a_2,\cdots ,a_N$이 공백으로 구분되어 주어진다. 각 $a_i$는 $i$번째 곡의 클리어 시간이다. (1ドル \leq i \leq N$)

셋째 줄부터 $Q$개의 줄에 걸쳐 쿼리에 대한 정보가 주어진다.

2ドル$번 쿼리는 한 번 이상 주어진다.

출력

2ドル$번 쿼리의 결과를 한 줄에 하나씩 출력한다.

제한

• 1ドル\leq N,Q\leq 200,円 000$
• 1ドル\leq a_i\leq 100,円 000$
• 1ドル\leq j\leq N+\text{(해당 쿼리 이전에 주어진 3번 쿼리의 개수)}$
• 1ドル\leq v\leq 100,円 000$
• 1ドル\leq T\leq 10^9$

입력으로 주어지는 모든 수는 정수이다.

힌트