問題文

非負整数 $X$ が与えられます。$X$ に対して以下の $2$ 種類の操作を行うことができます。

操作 $1:$ $X$ を $X + A$ に置き換える $\\$ 操作 $2:$ $X$ を $X$ or $A$ に置き換える

$Q$ 個のクエリに答えてください。$i$ 番目のクエリは以下です。

• $X$ に対して $A_1, A_2, ..., A_i$ について順に $1$ 回ずつ 操作 $1$ か 操作 $2$ を行う
• 操作 $2$ を行う回数はちょうど $K_i$ 回である必要がある
• 条件を満たしながら操作を行ったときの最大値を出力してください

制約

• $1 \leq Q \leq 3000$
• $0 \leq X, A_i \leq 10 ^ 9$
• $0 \leq K_i \leq i$

入力

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

X Q
A1 K1
A2 K2
  ⋮
AQ KQ

出力

$i$ 行目に $i$ 番目のクエリの結果を出力してください。

サンプル

0 3
5 1
3 1
2 2

5
8
10

クエリ $1$ では 操作 $2$ を行うことで $0$ or $5 = 5\\$ クエリ $2$ では 操作 $2,$ 操作 $1$ を順に行うことで $(0$ or $5)$ or $3 = 7\\$ クエリ $3$ では 操作 $2,$ 操作 $1,$ 操作 $2$ を順に行うことで $((0$ or $5) + 3)$ or $2 = 10\\$ が得られ、これらが最大です。