Su0ka game

• 入出力例3に余分な行が含まれていましたので修正しました。

問題文

moguさんはとあるゲームをしている。このゲームのルールは次の通りである。

• $N$ 種類の果物と箱がある。最初、箱に果物は入っていない。この箱の中に同じ種類の果物が $2$ つ以上入っているとき、そのような果物がなくなるまで次のことが起こる。

• $i$ 番目の種類の果物が $2$ つ以上ある場合、そのうちの $2$ つが合体して、$i+1$ 番目の種類の果物 $1$ つになる。ただし、 $i=N$ の場合は合体した果物が別の種類の果物になることなくそのまま消滅する。

moguさんは最初の状態から $Q$ 回次の操作を行う。ただし、文章中の $j$ はその操作が何番目の操作かを示している。

• (操作) 箱の中に、$a_j$ 番目の種類の果物を $c_j$ 個入れる。果物の合体が起こる場合は合体が最後まで終わるまで待つ。

$Q$ 回の操作が全て終わった後、箱の中に入っている果物の種類をすべて答えよ。$Q$ 回の操作後に箱の中に入っている果物の種類は果物の合体の順番によらず一意に定まることが証明できる。

制約

• $1 \leq N \leq 30$
• $1 \leq Q \leq 5 \times 10^{5}$
• $1 \leq a_j \leq N(1 \leq j \leq Q)$
• $1 \leq c_j \leq 10^{9}$

入力

入力はすべて整数である。

N Q
a_1 c_1
a_2 c_2
...
a_Q c_Q

出力

箱の中に入っている果物の種類を数字の昇順にすべて一行に出力せよ。

サンプル

3 3
1 1
3 1
1 2

1 2 3

$1$ つ目の操作のあと、箱の中には 種類 $1$ の果物が $1$ つ入っています。

$2$ つ目の操作のあと、箱の中には 種類 $1,3$ の果物が $1$ つづつ入っています。

$3$ つ目の操作で種類 $1$ の果物を $1$ つ入れたあと、箱の中には 種類 $1$ の果物が $3$ つ、種類 $3$ の果物が $1$ つ入っています。続いて、種類 $1$ の果物 $2$ つが合体して 種類 $2$ の果物 $1$ つ になり、どの種類の果物も$1$ つ以下となったので操作が終わります。箱の中には 種類 $1,2,3$ の果物が $1$ つづつ入っています。

$3$ 回の操作のあとに箱の中に入っている果物の種類は 種類 $1,2,3$ なので、1 2 3と出力します。

3 2
1 4
3 1

$1$ つ目の操作で種類 $1$ の果物を $4$ つ入れたあと、箱の中には 種類 $1$ の果物が $4$ つ入っています。続いて、種類 $1$ の果物 $2$ つが合体して 種類 $2$ の果物 $1$ つになり、同じことがもう一度起こって 種類 $2$ の果物が $2$ つになります。さらに、種類 $2$ の果物 $2$ つが合体して 種類 $3$ の果物 $1$ つになり、操作が終わります。箱の中には 種類 $3$ の果物が $1$ つ入っています。

$2$ つ目の操作で種類 $3$ の果物を $1$ つ入れたあと、箱の中には 種類 $3$ の果物が $2$ つ入っています。続いて、種類 $3$ の果物 $2$ つが合体して消滅し、操作が終わります。箱の中には果物がありません。 $2$ 回の操作のあとに箱の中には果物が入っていないので、空の行を出力してください。

10 6
1 1000
3 40
8 3
1 21
7 11
10 100

1 3 4 5 7 8