Alice and Bob are playing a game on a $$$1 \times n$$$ grid, where:

• Alice starts at cell $$$x$$$, Bob starts at cell $$$y$$$, where $$$1 \le x,y \le n$$$ and $$$x \neq y$$$.
• Alice and Bob alternate turns, with Alice moving first.
• A turn consists of exactly $$$3$$$ moves, where each move is either move one unit to the left or move one unit to the right.
• A player can't jump onto or over another player, and all moves cannot exceed the boundary.

For example, $$$n=8$$$, $$$x=4$$$ and $$$y=7$$$, where Alice moves first:

• $$$4 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$ is considered as Alice's valid moves.
• $$$4 \rightarrow 5 \rightarrow 6 \rightarrow 5$$$ is considered as Alice's valid moves.
• $$$4 \rightarrow 5 \rightarrow 6$$$ is considered as Alice's invalid moves because this violates the rule of exactly $$$3$$$ moves.
• $$$4 \rightarrow 5 \rightarrow 6 \rightarrow 7$$$ is considered as Alice's invalid moves because this violates the rule that a player can't jump onto another player.

A player loses if no valid move exists on their turn. The game terminates when a player cannot move.

Your task is to determine whether Alice will win, assuming that the strategies of the two players are optimal.

There is a regular $$$n$$$-sided shape with vertices labeled from $$$1$$$ to $$$n$$$ in clockwise order.

You can add a line segment with vertices $$$i$$$ and $$$j$$$ as endpoints only if:

• $$$|i-j| \gt 1$$$.
• $$$\gcd(i, j) = 1$$$.

Here $$$\operatorname{gcd}$$$ denotes the greatest common divisor.

Find the max number of line segments you can add such that no two segments intersect (except possibly at their endpoints).

Alyona always plays with the numbers and the numbers that are between two numbers. Alyona's teacher notices this and gives her a mini assessment.

The teacher gives her three numbers $$$n$$$, $$$l$$$, and $$$r$$$ ($$$l \le r$$$). Alyona has to find the minimum integer $$$x$$$ such that:

• $$$x \in [l,r]$$$.
• $$$\gcd(n,x) \in [l,r]$$$.

Here $$$\operatorname{gcd}$$$ denotes the greatest common divisor.

If there is no such integer $$$x$$$, output $$$-1$$$ instead.

There's a $$$1 \times n$$$ grid. For a string $$$y$$$ of length $$$l$$$, a robot moves according to the following pattern.

• Initially, the robot selects a cell as the starting point.
• Then, in the $$$i$$$-th $$$(1 \leq i \leq l)$$$ move, if $$$y_i = \mathtt{L}$$$, the robot moves one cell to the left; if $$$y_i = \mathtt{R}$$$, it moves one cell to the right. If the robot moves out of bounds, it explodes.

You are given a possibly incomplete string $$$x$$$ of length $$$m$$$. Your task is to complete the string $$$x$$$ such that, regardless of which cell the robot selects as the starting point, it will always explode. If there's no such string, output "NO" instead.

There is a classical problem: given an $$$n \times n$$$ grid, where the value of each cell $$$(i, j)$$$ is $$$a_{i,j}$$$. You need to find the path with the maximum sum from $$$(1, 1)$$$ to $$$(n, n)$$$ when you can only move right or down.

Support $$$q$$$ modifications: each modification gives an integer $$$k$$$, where $$$2 \le k \le 2n$$$. For all cells $$$(i, j)$$$ such that $$$i + j = k$$$ ($$$1 \le i$$$, $$$j \le n$$$), modify $$$a_{i,j}$$$ to $$$v$$$. You need to output the answer after each modification. Note the impact of a modification is permanent.

This is an interactive problem.

Alice and Bob are playing a bracket game with a sequence $$$s$$$. Initially, $$$s$$$ is empty. The game lasts for $$$n$$$ rounds in total.

In the $$$i$$$-th turn:

• If $$$i$$$ is odd, Alice adds exactly $$$a$$$ brackets (left or right bracket) to the back of $$$s$$$;
• Otherwise, Bob adds exactly $$$b$$$ brackets (left or right bracket) to the back of $$$s$$$.

After $$$n$$$ rounds, if $$$s$$$ is a regular bracket sequence, Alice wins. Otherwise, Bob wins.

It is guaranteed that $$$n$$$ is odd and both $$$a$$$ and $$$b$$$ are even.

A bracket sequence is called regular if it can be constructed by the following formal grammar.

1. The empty sequence $$$\varnothing$$$ is regular.
2. If the bracket sequence $$$A$$$ is regular, then $$$\mathtt{(}A\mathtt{)}$$$ is also regular.
3. If the bracket sequences $$$A$$$ and $$$B$$$ are regular, then the concatenated sequence $$$A B$$$ is also regular.

For example, the sequences "(())()", "()", "(()(()))", and the empty sequence are regular, while "(()" and "(()))(" are not.

Choose to be Alice or Bob, and play the game with the jury.

The first line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$3 \le n \le 49$$$, $$$2 \le a,b \le 50$$$). It is guaranteed that $$$n$$$ is odd and both $$$a$$$ and $$$b$$$ are even.

To choose to be Alice or Bob, you need to print an integer $$$x$$$ $$$(0 \le x \le 1)$$$, where $$$x=1$$$ means you choose Alice, and $$$x=0$$$ means you choose Bob.

If you choose to be Alice, you need to output a string containing exactly $$$a$$$ brackets in each $$$i$$$-th turn, where $$$i$$$ is odd. And read Bob's string containing exactly $$$b$$$ brackets in each $$$i$$$-th turn, where $$$i$$$ is even.

If you choose to be Bob, you need to output a string containing exactly $$$b$$$ brackets in each $$$i$$$-th turn, where $$$i$$$ is even. And read Alice's string containing exactly $$$a$$$ brackets in each $$$i$$$-th turn, where $$$i$$$ is odd.

After printing a query or the answer for a test case, do not forget to output the end of line and flush the output. Otherwise, you will get the verdict Idleness Limit Exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

Hacks

To hack, follow the test format below.

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$).

The first line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$3 \le n \le 49$$$, $$$2 \le a,b \le 50$$$).

It must be guaranteed that $$$n$$$ is odd and both $$$a$$$ and $$$b$$$ are even.

You are given three integers $$$n$$$, $$$L$$$, and $$$R$$$.

You need to do the following:

• Pick an integer $$$m$$$ such that $$$1 \leq m \leq n$$$;
• Partition the interval $$$[1, n]$$$ into $$$m$$$ intervals $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$ such that:
  • $$$l_1 = 1$$$ and $$$r_m = n$$$;
  • $$$l_i \leq r_i$$$ for all $$$1 \leq i \leq m$$$;
  • $$$r_i = l_{i+1} - 1$$$ for all $$$1 \leq i \lt m$$$;
  • $$$L \leq r_i - l_i + 1 \leq R$$$.

Note $$$P_i= \Pi_{l_i}^{r_i}i$$$. Find the minimum of $$$\gcd(P_1, P_2,\ldots,P_m)$$$, and output your interval partition scheme. Here, $$$\gcd$$$ means greatest common divisor.

For example, $$$n=7$$$, $$$L=3$$$ and $$$R=4$$$, one optimal scheme is to choose $$$m=2$$$ and intervals $$$[1,4]$$$ and $$$[5,7]$$$. In this case, $$$\gcd(P_1,P_2)=\gcd(1 \cdot 2 \cdot 3 \cdot 4,5 \cdot 6 \cdot 7)=\gcd(24,210)=6$$$, which can be proven to be the minimum value.

Since the value of $$$\gcd(P_1, P_2,\ldots,P_m)$$$ may be large, you need to output it modulo $$$998\,244\,353$$$. If there is not any valid interval partition scheme, output $$$-1$$$ instead.

You're given two integers $$$n$$$ and $$$q$$$ and two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$.

You need to answer $$$q$$$ queries. In the $$$i$$$-th query, you're given three integers $$$k_i, l_i$$$, and $$$r_i$$$.

At first, a variable $$$x$$$ is set to $$$k_i$$$. Then, for each $$$j$$$ from $$$l_i$$$ to $$$r_i$$$, you must choose exactly one of the following two types of operations:

1. set $$$x := x + a_j$$$;
2. set $$$x := \max(x, b_j)$$$.

You need to find the maximum possible value of $$$x$$$ for each query.