This is an IOI-style interactive problem.

Since PJudge is headless, the Fish King Qingyu and his capable assistant, the headless fish, are playing with several problem-generating AIs today.

Description

The Fish King Qingyu used GameGPT to generate a game.

Now, Qingyu and the headless fish are playing the following game: There are several pairs of stone piles. Initially, in the $i$-th pair, the two piles contain $a_i$ stones each. In each round, Qingyu can choose one pile and remove any positive integer number of stones from it. In each round, the headless fish can choose one pile and move any positive integer number of stones from it to the pile it is paired with. Qingyu moves first. The game ends when all stone piles are empty. Qingyu wants the game to be as short as possible, while the headless fish wants the game to be as long as possible. Calculate the total number of operations performed if both players play optimally.

Qingyu fed this game into OIGPT as well, so you also need to support point updates on $a$ and answer queries for the above problem over a range of $a$.

Let $n$ be the sequence length and $q$ be the number of operations, where $n, q \leq 5 \times 10^6$.

Interaction

You do not need to, and should not, implement the main function. You must include #include "game.h" and implement the following three functions:

• void build(std::vector<long long> a, bool flag): This function will be called at the beginning of each test case. The parameters are the sequence $a$ (1-indexed, a[0] is $0$) and a flag indicating whether there are update operations. $flag=0$ means there are no updates, otherwise there are. You can use a.size()-1 to get $n$. You do not know $q$ at this time.

• void modify(int p, long long x): This indicates that $a_p$ is updated to $x$.

• int query(int l, int r): This indicates a query for the answer in the range $[l, r]$.

It is guaranteed that build is called exactly once per execution, and all calls to modify and query occur after build.

To facilitate debugging, a sample interactive library is provided. You can place game.h, implementer.cpp, and your code (assuming it is named code.cpp) in the same folder and compile using g++ code.cpp implementer.cpp -o code -std=c++14 -O2 (for Windows users, use g++ code.cpp implementer.cpp -o code.exe -std=c++14 -O2 -Wl,--stack=2147483647).

Sample interactive library input format:

The first line contains four numbers $n, q, flag, t$, where $q$ is the number of operations and $t$ is a parameter regarding the output format.

The next line contains $n$ numbers, representing the initial sequence.

The next $q$ lines each contain three numbers $o, x, y$, where $o=1$ means querying the answer for range $[x, y]$, and $o=2$ means updating $a_x$ to $y$.

Sample interactive library output format:

If $t=1$, for each query, output the answer on a single line. If $t=0$, output the string hash of all query answers. You can read implementer.cpp to understand the specific hashing method.

It is guaranteed that the interactive library used in actual testing will take no more than $1/10$ of the time limit and no more than $1/3$ of the memory limit of the corresponding test case.

Examples

Input 1

4 1 0 1
3 3 3 3
1 1 4

Output 1

21

Note 1

This is a possible process of the game where every step is optimal. The numbers represent the stone counts in each pile, with every two piles forming a pair.

3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 0
3 3 3 3 3 3 1 2
3 3 3 3 3 3 1 0
3 3 3 3 3 3 0 1
3 3 3 3 3 3 0 0
3 3 3 3 2 4 0 0
3 3 3 3 2 0 0 0
3 3 3 3 1 1 0 0
3 3 3 0 1 1 0 0
3 3 1 2 1 1 0 0
3 3 1 0 1 1 0 0
3 3 0 1 1 1 0 0
3 3 0 0 1 1 0 0
2 4 0 0 1 1 0 0
2 0 0 0 1 1 0 0
1 1 0 0 1 1 0 0
1 0 0 0 1 1 0 0
0 1 0 0 1 1 0 0
0 0 0 0 1 1 0 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0

Input 2

8 10 0 1
1 3 1 4 1 3 1 4 
1 5 7
1 2 3
1 2 5
1 2 3
1 2 4
1 2 8
1 4 7
1 5 6
1 3 8
1 2 6

Output 2

9
7
15
7
13
29
15
7
23
21

Examples 3~5

Please see the provided files.

Constraints

There are 20 test cases in total, each worth an equal share of points.

Unless otherwise specified, the memory limit is 128 MB and the time limit is 1 s.

• For the 1st test case, there are no queries.
• For the first 3 test cases, $n \leq 8, a_i \leq 4, q \leq 100$.
• For the 4th test case, for some $k$ and all $i$, $a_i = 2^k$.
• For the 5th test case, for some $k$ and all $i$, $a_i = 2^k - 1$.
• For the 6th test case, $n, q \leq 1000$.
• For the first 8 test cases, there are no modifications.
• For the 9th, 10th, and 11th test cases, the memory limit is 1024 MB and the time limit is 3 s.
• For the 12th, 13th, and 14th test cases, the time limit is 3 s.
• For the first 16 test cases, $n, q \leq 2 \times 10^6$.
• For the 17th, 18th, 19th, and 20th test cases, $n, q \leq 5 \times 10^6$, the memory limit is 512 MB, and the time limit is 3 s.
• For all test cases, $n, q \leq 5 \times 10^6, n \geq 1, 0 < a_i < 2^{40}$.

Please pay attention to the memory limits.