問題文

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

操作 1:1: XXX+AX + A に置き換える \\ 操作 2:2: XXXX or A A に置き換える

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

  • XX に対して A1,A2,...,AiA_1, A_2, ..., A_i について順に 11 回ずつ 操作 11 か 操作 22 を行う
  • 操作 22 を行う回数はちょうど KiK_i 回である必要がある
  • 条件を満たしながら操作を行ったときの最大値を出力してください

制約

  • 1Q30001 \leq Q \leq 3000
  • 0X,Ai1090 \leq X, A_i \leq 10 ^ 9
  • 0Kii0 \leq K_i \leq i

入力

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

X Q
A1 K1
A2 K2
  ⋮
AQ KQ

出力

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

サンプル

入力1
0 3
5 1
3 1
2 2
出力1
5
8
10

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

Submit


Go (1.21)