You and your classmates found three problems to practice on.

The goal of this practice is to write code that can process as large a scale of data as possible within the time limit.

Your classmates have written excellent code. Now, they issue a challenge to you: for each problem, they set several test cases, which are the largest scale of test data their code can pass. Now, they want to see how many of their codes your code can beat by passing larger scale test data.

This problem is divided into 3 tasks, each corresponding to one problem and several test cases. For each task, you need to design a program that can pass as many test points as possible.

Task 1

Given $n$ 32-bit unsigned integers, sort them from smallest to largest.

Task 2

There are $2n$ people playing the "Rock Paper Scissors" game. They line up in two rows, each row containing $n$ people. Every person uses a fixed strategy in every round of the game, i.e., for the $j$-th ($0 \le j < n$) person in the $i$-th ($i \in \{1, 2\}$) row, an integer $a_{i, j}$ represents their strategy, where $0$ represents Rock, $1$ represents Scissors, and $2$ represents Paper.

Now there are $q$ queries. Each query gives three integers $x, y, l$ ($0 \le x, y < n$, $1 \le l \le n - \max(x, y)$). Ask: after the $x \sim x+l-1$-th people of the first row play matches against the $y \sim y+l-1$-th people of the second row, how many people in the first row will win?

Here, a "match" means that for all integers $i$ satisfying $0 \le i < l$, the $(x+i)$-th person in the first row plays a "Rock Paper Scissors" game against the $(y+i)$-th person in the second row.

Task 3

We call a valid bracket sequence a string consisting only of left brackets ( and right brackets ) such that the counts of both types of brackets are equal, and any prefix contains no fewer left brackets than right brackets. Now given a string consisting of (, ) and ?, how many different ways are there to replace every ? with a bracket such that the string becomes a valid bracket sequence? Two ways are different if and only if at least one ? is replaced by a different bracket.

Since the data scale of tasks in this problem is large, we use some special methods for input and output. First, let's define some functions for input/output (in the code below, division truncates towards zero, array indices start from 0, XOR is bitwise XOR, right shift is logical right shift).

Define function next_integer(32-bit unsigned integer x):
    Assign x to x XOR (x left-shift 13)
    Assign x to x XOR (x right-shift 17)
    Assign x to x XOR (x left-shift 5)
    Return x

Define function output_arr(pointer a, 32-bit unsigned integer size):
    If (size mod 4) is not equal to 0:
        Output -1
        Return false
    Let 32-bit unsigned integer count = size / 4
    Let 32-bit unsigned integer pointer b = a cast to 32-bit unsigned integer pointer
    Let 32-bit unsigned integer ret = size
    Let 32-bit unsigned integer x = 23333333
    For 32-bit unsigned integer i from 0 to count - 1:
        Assign ret to ret XOR (b[i] + x)
        Assign x to next_integer(x)
    Output ret
    Return true

Input

Read input from challenge.in.

The first line contains an integer task_id ($1 \le \text{task\_id} \le 3$), representing the task ID. Next is the input content for each specific task.

In the same line of input, adjacent integers are separated by a space.

For Task 1: One line with two integers $n, s$. Let $a_0 = \text{next\_integer}(s)$, $a_i = \text{next\_integer}(a_{i-1})$ ($1 \le i < n$), then $a_0, a_1, \dots, a_{n-1}$ are the $n$ integers to be sorted.

For Task 2: The first line contains two integers $n, q$. The second line contains a string of length $n$ consisting only of '0', '1', '2'. The $i$-th character represents the integer strategy of the $i$-th person in the first row (i.e., $a_{1, i}$). The third line has the same format as the second line, representing the strategies of each person in the second row.

For Task 3: The first line contains an integer $n$, representing the length of the given string. The second line contains a string, which is the given string.

Output

Output to challenge.out.

For Task 1: Let $b_0, b_1, \dots, b_{n-1}$ be the sorted array, simply call output_arr(b, n * 4).

For Task 2: Store the answer for each query sequentially into a 32-bit unsigned integer array $b$ (i.e., stored into $b_0, b_1, \dots, b_{q-1}$), then simply call output_arr(b, q * 4).

For Task 3: Output an integer representing the number of different ways modulo $2^{32}$.

Data Range and Constraints

There are 9 test cases in total. Different test cases may have different point values. For each test case, you get full points if and only if your output is completely identical to the standard output. Below is the table of data ranges and constraints for each test case. For ease of reading, the "Test Case ID" column is placed in the middle of the table instead of the left.

Hints and Notes

The -O2 optimization flag is enabled for all languages.

Due to evaluation machine performance differences, the time limit for Test Case 3 is changed to 5.0 seconds, while the time limit for all other test cases is 3s. The memory limit for all test cases is 2GB (for 32-bit computers, this limit is the upper bound of memory usable by a single program).

Evaluation is performed on this machine. Please note that the configuration and model of all machines are identical.

For each programming language, we provide a template program that only implements input/output functions, named challenge_model.pas/c/cpp. You may start solving the problem based on this template program, or you may choose not to use it; this is unrelated to your score.

We provide some sample input/output files named challenge1.in/ans ~ challenge9.in/ans, where the input data scale of the $i$-th pair of files is identical to the data scale of the $i$-th test case. See 【Data Range and Constraints】 for the data scale of each test case.

Please note that according to relevant regulations of the NOI series competitions, your submitted code length cannot exceed 100KB.

Detailed Task Explanation

We provide detailed explanations here for some parts of the tasks that might cause confusion.

For Task 1:

A 32-bit unsigned integer occupies 32 binary bits (or 4 bytes) of memory. It is unsigned int in C/C++, and dword in Pascal.

Sorting from smallest to largest means rearranging the $n$ integers $a_0, a_1, \dots, a_{n-1}$ into $b_0, b_1, \dots, b_{n-1}$ such that for any $1 \le i < n$, $b_{i-1} \le b_i$.

For Task 2:

The rule of "Rock Paper Scissors" is that Rock beats Scissors, Scissors beats Paper, and Paper beats Rock; non-winning outcomes are not counted as wins.

In input data and queries, the index of each row starts from 0, i.e., "the $x$-th person ($0 \le x < n$)" refers to the $(x+1)$-th person counting from left to right in that row.

For Task 3:

We give some examples of bracket sequences: (())() is valid, (((()()))) is also valid; (((( is invalid, ())( is also invalid.

For input data (???, the answer is 2, with (()) and ()() as the two valid ways. For input data )???, the answer is 0, because it is impossible to have a valid bracket sequence starting with a right bracket.