AT_abc403_g [ABC403G] Odd Position Sum Query

空の数列 $ A $ があります。 $ Q $ 個のクエリが与えられるので順に処理してください。 $ i $ 番目のクエリは以下で説明されます。 > 整数 $ y_i $ が与えられる。 $ z $ を $ i=1 $ のときは $ 0 $ 、それ以外のときは $ i-1 $ 番目のクエリに対する答えとし、 $ x_i $ を $ x_i=((y_i+z)\bmod 10^9)+1 $ で定義する。 $ A $ の末尾に $ x_i $ を追加する。 > その後、 $ A $ を昇順に並べた列を $ B=(B_1,B_2,\ldots,B_i) $ としたとき $ B $ の奇数番目の要素の総和を求めよ。すなわち、 $ i $ 以下の最大の奇数を $ m $ としたとき $ B_1+B_3+B_5+\ldots+B_m $ を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ y_1 $ $ y_2 $ $ \vdots $ $ y_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 - $ 1 $ つ目のクエリについて、 $ y_1=1,z=0 $ であるため $ x_1=((1+0)\bmod 10^9)+1=2 $ です。 $ A $ の末尾に $ x_1 $ を追加すると $ A=(2) $ となります。 $ A $ を昇順に並べた列 $ B $ は $ B=(2) $ であるため、求める値は $ B_1=2 $ です。 - $ 2 $ つ目のクエリについて、 $ y_2=3,z=2 $ であるため $ x_2=((3+2)\bmod 10^9)+1=6 $ です。 $ A $ の末尾に $ x_2 $ を追加すると $ A=(2,6) $ となります。 $ A $ を昇順に並べた列 $ B $ は $ B=(2,6) $ であるため、求める値は $ B_1=2 $ です。 - $ 3 $ つ目のクエリについて、 $ y_3=1,z=2 $ であるため $ x_3=((1+2)\bmod 10^9)+1=4 $ です。 $ A $ の末尾に $ x_3 $ を追加すると $ A=(2,6,4) $ となります。 $ A $ を昇順に並べた列 $ B $ は $ B=(2,4,6) $ であるため、求める値は $ B_1+B_3=8 $ です。 - $ 4 $ つ目のクエリについて、 $ y_4=999999994,z=8 $ であるため $ x_4=((999999994+8)\bmod 10^9)+1=3 $ です。 $ A $ の末尾に $ x_4 $ を追加すると $ A=(2,6,4,3) $ となります。 $ A $ を昇順に並べた列 $ B $ は $ B=(2,3,4,6) $ であるため、求める値は $ B_1+B_3=6 $ です。 - $ 5 $ つ目のクエリについて、 $ y_5=999999993,z=6 $ であるため $ x_5=((999999993+6)\bmod 10^9)+1=1000000000 $ です。 $ A $ の末尾に $ x_5 $ を追加すると $ A=(2,6,4,3,1000000000) $ となります。 $ A $ を昇順に並べた列 $ B $ は $ B=(2,3,4,6,1000000000) $ であるため、求める値は $ B_1+B_3+B_5=1000000006 $ です。 ### Sample Explanation 2 $ x_1,x_2,\ldots,x_8 $ の値は順に以下の通りです。 ``` 105282054 800516877 573289179 26509423 168629803 696409999 656737335 915059758 ``` ### Constraints - $ 1\leq Q\leq 3\times 10^5 $ - $ 0\leq y_i\lt 10^9 $ - $ 1\leq x_i\leq 10^9 $ - 入力は全て整数