Given three positive integers $$$p_A,p_B,p_C$$$, Bobo challenges you to find out three infinite binary strings $$$A,B,C$$$ with period $$$p_A$$$, $$$p_B$$$ and $$$p_C$$$ respectively satisfying $$$A \oplus B = C$$$, or determine it is impossible to do so.

Please refer to the Note section for the formal definition of period and exclusive or.

Bobo has been playing a puzzle called Rolling Stones, which takes place on an equilateral triangular board consisting of $$$n$$$ $$$(n\geq 2)$$$ rows and $$$n^2$$$ cells. Each cell on the board is labeled with a number from $$$1$$$ to $$$4$$$. Bobo also has a tetrahedral stone, with each face numbered from $$$1$$$ to $$$4$$$ (a tetrahedral dice), initially placed at the first cell in the first row of the board. The position of the stone is as follows: the face with the number $$$1$$$ is towards the left, the face with the number $$$2$$$ is towards the next row, the face with the number $$$3$$$ is towards the right, and the face with the number $$$4$$$ is on the bottom side.

The goal of the puzzle is to roll the stone to a target cell under the following rules:

• Matching Numbers: When the stone rests on a cell, the number on the cell must match the number on the stone's bottom face.
• Single Visit: Each cell can only be visited once throughout the journey, including the starting and target cells.

The illustration for a solution of the first sample test is given as follows.

Illustration

Bobo is exploring a set of lattice points on a two-dimensional plane. Initially, the set of points is defined as $$$S = \{(0,0),(A,0),(0,B),(A,B)\}$$$. Bobo's goal is to include a specific lattice point $$$(X,Y)$$$ in $$$S$$$. To achieve the goal, Bobo may perform the following operation:

• Select two lattice points $$$P,Q \in S$$$ such that $$$\frac{P+Q}{2}$$$ is also a lattice point, and add $$$\frac{P+Q}{2}$$$ to $$$S$$$.

Your task is to help Bobo find a sequence of operations that minimizes the number of steps to achieve the goal or determine if it is impossible to do so.

Alice and Bobo are engaged in an intriguing game, and you have the honor of being the judge.

In the $$$k$$$-th round, you will write down a pair of integers $$$(a_k, b_k)$$$ on the blackboard, clearly visible to both Alice and Bobo. Once they see the numbers, you will secretly select an integer $$$1 \leq i \leq k$$$, giving $$$a_i$$$ to Alice and $$$b_i$$$ to Bobo. The excitement builds as Alice and Bobo take turns either claiming they know the other's number or admitting that they do not know the answer, starting with Alice. The player who correctly guesses the other's number first will win the game!

Both players are exceptionally smart and honest, making the game all the more captivating. As you observe their interactions, you can't help but wonder: in the $$$k$$$-th round, how many values of $$$i$$$ that Alice wins, and how many values of $$$i$$$ that Bobo wins?

Bobo is given a tree $$$T = (V, E)$$$ of $$$n$$$ vertices, where there is a number $$$p_i$$$ on vertex $$$i$$$ initially, and $$$p_1,p_2,\dots,p_n$$$ is a permutation of $$$1$$$ to $$$n$$$, meaning that all integers from $$$1$$$ to $$$n$$$ appear exactly once in $$$p_1,p_2,\dots,p_n$$$

In each operation, Bobo can select a matching $$$M \subseteq E$$$ ($$$M$$$ is a matching means that no two edges in $$$M$$$ share a common vertex), and for each $$$(u, v) \in M$$$, swap the number on vertex $$$u$$$ and vertex $$$v$$$ (i.e. swap $$$p_u$$$ and $$$p_v$$$).

Bobo wants to use at most $$$3n$$$ operations to make $$$p_i=i$$$ for each $$$1 \le i \le n$$$, can you please help him?

Bobo is trapped in an infinite time loop of a peculiar day! Each day consists of exactly $$$k$$$ hours, and every day, $$$n$$$ tasks arrive for Bobo to complete.

• The $$$i$$$-th task of the day arrives at the beginning of the $$$a_i$$$-th hour and requires $$$b_i$$$ hours of uninterrupted effort to finish.
• Bobo works diligently and always follows a disciplined approach: whenever there are unfinished tasks, Bobo works on the earliest received unfinished task.

At the beginning of the first day, Bobo starts with no tasks.

Your mission is to help Bobo answer $$$q$$$ queries. For the $$$i$$$-th query, you are given $$$x_i$$$, the day on which a task is received, and $$$y_i$$$, the index of the task received on that day. Your goal is to determine the exact day and hour when Bobo will complete the $$$y_i$$$-th taskof day $$$x_i$$$.

Bobo is working with an integer sequence $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$. He must process $$$q$$$ queries in order. Each query is of one of the following two types:

• 1 $$$L$$$ $$$R$$$ $$$v$$$ ($$$1 \le L \le R \le n$$$, $$$0 \le v \le 2 \cdot 10^5$$$): for all $$$i \in [L,R]$$$, update $$$a_i \gets a_i + v$$$;
• 2 $$$L$$$ $$$R$$$ ($$$1 \le L \lt R \le n$$$, $$$R-L+1$$$ is even): determine if elements $$$a_L, a_{L+1}, \ldots, a_R$$$ can be divided into $$$(R-L+1)/2$$$ pairs of integers with the same sum.

Your task is to help Bobo process these queries efficiently.

During his spare time, Bobo likes to play puzzle games a lot. His favorite one is The Witness, an acclaimed 2016 puzzle video game designed by Jonathan Blow. The Witness contains 9 principal types of puzzles and several hidden "environmental" puzzles, totaling an amount of 664 puzzles spread over the open world of the game. A player is invited to explore the world and to deduce the rules of various puzzles they encounter.

Among all types of puzzles, Bobo expertizes at a certain type called the "Black and White Squares" puzzle. This kind of puzzle is based on a rectangular grid and requires the player to connect a starting point to an end point with a simple grid path while splitting the grid cells of two different colors. The following are some real examples of this type of puzzle in-game together with one of their solutions. The starting point and the end point are marked with circles and a protruding semicircle from the grid, respectively.

Given an instance of the "Black and White Squares" puzzle such that all cells are either black or white, Bobo decides to leave you the challenge: can you provide a solution to the puzzle or assert there are none?

Formally, an instance of the "Black and White Squares" puzzle is described by the following:

• two positive integers $$$n,m$$$, representing the number of rows and columns of the rectangular grid. There are then $$$n\times m$$$ cells and $$$(n+1)\times (m+1)$$$ vertices in the grid. We label the vertex on the upper-left corner of the grid as $$$(0,0)$$$, the vertex on the lower-right corner of the grid as $$$(n,m)$$$, and the rest accordingly.
• An $$$n\times m$$$ two-dimensional array, representing the color of each cell. The color of each cell can only be either black or white.
• A starting point $$$(sx,sy)$$$ and an end point $$$(ex,ey)$$$ , each belonging to one of the vertices on the border of the grid. Here a vertex $$$(x,y)$$$ is on the border means at least one of the following is satisfied:
  • $$$x=0$$$
  • $$$x=n$$$
  • $$$y=0$$$
  • $$$y=m$$$
  Also, the starting point and the end point cannot coincide.

A solution to the "Black and White Squares" puzzle is described by a path $$$P=((x_1,y_1),(x_2,y_2),\dots,(x_{\ell},y_{\ell}))$$$ $$$(\ell\geq 2)$$$ satisfying the following properties:

• $$$(x_1,y_1)=(sx,sy)$$$ and $$$(x_{\ell},y_{\ell})=(ex,ey)$$$.
• For each $$$2\leq i\leq \ell$$$, it follows $$$(x_{i-1},y_{i-1})$$$ and $$$(x_{i},y_{i})$$$ are adjacent on the grid, i.e. one of the following is satisfied:
  • $$$x_{i}=x_{i-1}$$$ and $$$| y_i-y_{i-1}|=1$$$
  • $$$| x_{i}-x_{i-1}|=1$$$ and $$$y_i=y_{i-1}$$$
• $$$P$$$ is simple, i.e., for each $$$1\leq i \lt j\leq \ell$$$, either $$$x_i\neq x_j$$$ or $$$y_i\neq y_j$$$.
• Each region of the grid separated by the path contains only one color.

Bobo is analyzing a group of $$$n$$$ people, where the $$$i$$$-th $$$(1\leq i\leq n)$$$ person has two attributes, $$$ x_i $$$ and $$$ y_i $$$. The attribute values of different people are distinct. For any two persons $$$1\leq i,j\leq n$$$ ($$$i \neq j$$$), Bobo defines their friend index $$$\mathrm{Friend}(i,j)$$$ and enemy index $$$\mathrm{Enemy}(i,j)$$$ respectively as follows:

$$$$$$ \mathrm{Friend}(i,j) \triangleq \max(|x_i - x_j|, |y_i - y_j|), \quad \mathrm{Enemy}(i,j) \triangleq |x_i - x_j| + |y_i - y_j| . $$$$$$ For any $$$1\leq i,j\leq n$$$ ($$$i \neq j$$$), Bobo calls the $$$j$$$-th person is a best friend of the $$$i$$$-th person if $$$$$$ \text{ for all }1 \leq k \leq n\text{ }(k \neq i), \quad \mathrm{Friend}(i,k) \geq \mathrm{Friend}(i,j). $$$$$$

Also, for any $$$1\leq i,j\leq n$$$ ($$$i \neq j$$$), Bobo calls the $$$j$$$-th person is a worst enemy of the $$$i$$$-th person if $$$$$$ \text{ for all }1 \leq k \leq n\text{ }(k \neq i), \quad \mathrm{Enemy}(i,k) \leq \mathrm{Enemy}(i,j). $$$$$$

Now Bobo wants to find out, for each $$$1 \leq t \leq n$$$, how many ordered pairs $$$ (i, j) $$$ satisfy $$$ 1 \leq i, j \leq t $$$, $$$ i \neq j $$$, and the $$$j$$$-th person is both a best friend and a worst enemy of the $$$i$$$-th person if we only consider the first $$$t$$$ people.

Please be aware of the unusual memory limit.

Bobo is participating in a weird tournament with $$$2n$$$ players, labeled $$$1$$$ through $$$2n$$$. Initially, all players have a score of zero. The tournament consists of $$$k$$$ rounds, and in each round, players are paired for one-on-one matches.

The scoring mechanism is as follows: after each match, the player with the higher score loses $$$1$$$ point, while the player with the lower score gains $$$1$$$ point. If two players have the same score, the player with the lower label (i.e., the smaller number) is considered the winner and gains $$$1$$$ point, while the other player loses $$$1$$$ point.

To ensure balance and to make the tournament more exciting, the host decided that the absolute value of any player's score must never exceed $$$3$$$ at any point in the tournament. Given these rules, Bobo wants to determine the number of possible ways to arrange the matches over the $$$k$$$ rounds.

As the answer might be too large, you should output the answer modulo $$$P$$$, which is a specified prime number.

Bobo is playing a game called Brotato. The game consists of $$$n$$$ levels, each of which he can either pass or fail. Each level has a probability $$$p$$$ of failure and a probability $$$1-p$$$ of passing. If Bobo fails a level, he must normally restart from the first level.

Bobo is quite frustrated about the fact that each time he dies, he has to start over from the very beginning. Therefore, Bobo decided to cheat. Now, Bobo has $$$k$$$ special items that allow him to continue from the same level after a failure rather than restarting from the beginning.

Given this setup, determine the minimum expected number of attempts for levels needed for Bobo to complete all $$$n$$$ levels.

Welcome to the China Collegiate Programming Contest (CCPC) Zhengzhou onsite! Bobo has noticed that the initials of "Zheng" and "Zhou" are both Z. This motivates him to study the well-known Z-order curve.

To introduce the Z-order curve, we first introduce the Moser–de Bruijn sequence $$$(B_t)_{t \ge 0}$$$, the ordered sequence of numbers whose binary representation has nonzero digits only in the even positions. The first few terms of the Moser-de Bruijn sequence are $$$0, 1, 4, 5, 16, 17, 20, 21$$$.

Each non-negative integer $$$z$$$ can be uniquely decomposed into the sum of $$$B_x$$$ and $$$2B_y$$$. Therefore, we can write down all natural numbers in an infinitely large table. The Z-order curve is then obtained by connecting all the numbers in numerical order.

Illustration of Z-curve

Bobo now challenges you with the following problem: For a given fragment extracted from the Z-curve from $$$L$$$ to $$$R$$$, find the smallest integer $$$l$$$ such that the Z-curve from $$$l$$$ to $$$l+R-L$$$ is identical to the given fragment (i.e., the curve from $$$l$$$ to $$$l+R-L$$$ can be obtained by translating the curve from $$$L$$$ to $$$R$$$).

Please note that in this problem, the curve is directed. Specifically, the curve from $$$1$$$ to $$$2$$$ is NOT identical to the curve from $$$3$$$ to $$$4$$$.

Bobo wants to use a rejection sampling algorithm to construct a random set $$$T\subset \{1,2,\dots,n\}$$$ of size $$$k$$$. For parameters $$$p_1,p_2,...,p_n$$$ $$$(0\leq p_i\leq 1)$$$ and integer $$$k$$$, the rejection sampler is defined as follows:

1. Initialize $$$T \gets \emptyset$$$;
2. For each $$$i$$$ $$$(1\leq i\leq n)$$$, add $$$i$$$ into $$$T$$$ with probability $$$p_i$$$;
3. Output $$$T$$$ if the size of $$$T$$$ is exactly $$$k$$$; otherwise, repeat the process.

Now you are given integers $$$a_1,a_2,...,a_n$$$ and $$$k$$$. Bobo needs to set the parameters $$$p_1,p_2,\ldots,p_n$$$ satisfying

• $$$\sum_{i=1}^n p_i=k$$$;
• for all $$$S\subseteq \{1,2,\cdots, n\}$$$ such that $$$|S|=k$$$, the probability that the rejection sampler outputs $$$S$$$ is proportional to $$$\prod_{i \in S} a_i$$$.

Your task is to find out the parameters $$$p_1,p_2,\dots,p_n$$$ for Bobo. It is guaranteed that such parameters exist and are unique. Your answer will be considered correct if the absolute error of each $$$p_i$$$ doesn't exceed $$$10^{-6}$$$ compared to the unique answer.