Walking on Segment Tree

$1$부터 $N$까지 번호가 붙은 상자가 있다. $i$번 상자에는 처음에 $A_i$개의 공이 들어 있다.

$Q$개의 쿼리를 순서대로 처리하라. 쿼리는 다음 중 하나이다.

• 1 i x: $i$번 상자에 공 $x$개를 추가한다. $(1 \leq i \leq N$, $1 \leq x \leq 10^9)$
• 2 k: 모든 공을 상자 번호가 작은 순서대로 나열했을 때 $k$번째 공이 들어 있는 상자의 번호를 출력한다. $(1 \leq k \leq$ 현재 모든 상자에 들어 있는 공의 개수의 합)

첫 번째 줄에 상자의 개수 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 \leq N,Q \leq 1\,000\,000)$

두 번째 줄에 각 상자에 들어 있는 공의 개수 $A_1,A_2,\ldots,A_N$이 주어진다. $(0 \leq A_i \leq 10^9)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.

2 k 쿼리마다 $k$번째 공이 들어 있는 상자의 번호를 한 줄에 하나씩 출력한다.