Lope the Bear often watches game events. He has a special skill: Dunai, also known as poisoned milk. Every time he predicts the outcome of a game by wishing the team that he believes will win good luck, the outcome often turns out to be the opposite. Recently, a tournament called Daota 2 The International is about to start. It's time for Lope to show his Dunai skill again.

In the game Daota 2, each team has five players corresponding to five positions, numbered from $$$1$$$ to $$$5$$$. Daota 2 The International has been held for $$$n$$$ editions. To better Dunai, Lope looks up the champion team of each edition, including the names and positions of the five players. In addition, he inquires about the $$$m$$$ players involved in the upcoming tournament including their names and positions, without knowing exactly how the teams will be formed. What is known is that for every player who has won a championship, his position in the team never changes.

Lope wants to predict how these $$$m$$$ players will be teamed up in a way that satisfies the following conditions:

• Each player is assigned to at most one team (possibly not assigned).
• The team consists of five different positions, with exactly one player for each position.
• Each team includes at least one player who has won a championship.

Lope wants to know the maximum number of teams that can be formed.

Cody the Wolf is the coach of a programming competition team. With the new contest season approaching, Cody intends to recruit some new members to the team. He prepares a programming problem for this recruitment:

• There is an expression with $$$n$$$ positive integers and $$$n-1$$$ plus signs $$$a_1+a_2+\dots+a_n$$$. We replace one plus sign $$$+$$$ with a multiplication sign $$$\times$$$ each time and perform $$$n-1$$$ times in total. Please calculate the result of the expression after each replacement.

Cody has generated the standard input and output files for this problem. But he deletes all the standard input files by mistake. Overwhelmed, Cody wonders if he can regenerate the corresponding input files while leaving the output files unchanged.

Formally, given $$$n$$$ integers $$$s_0,s_1,\dots,s_{n-1}$$$, where $$$s_i$$$ indicates the result of the expression after the $$$i$$$-th replacement, you need to construct an initial expression $$$a_1+a_2+\dots+a_n$$$ and determine the position of the plus sign for each replacement such that the result of each replacement matches the given integers $$$s_0,s_1,\dots,s_{n-1}$$$.

Charles the Rabbit likes eating grass. As the saying goes, rabbits do not eat the grass by their burrows. Therefore, Charles has to go outside his burrow every day to look for grass to eat.

One day, Charles comes to a two-dimensional plane with many distinct points. He can choose a point $$$A$$$ and another four points $$$B, C, D, E$$$ to connect with $$$A$$$ to form four segments. We consider these four segments as a clump of grass if they meet the following condition:

• Any two of the four segments have only a single point of intersection $$$A$$$ between them.

For example, in the picture below, $$$(1)$$$ is a clump of grass, but $$$(2)$$$ is not one as the intersection of segments $$$AC$$$ and $$$AE$$$ is not only a single point $$$A$$$.

Given $$$n$$$ points on a plane, Charles wants to know whether there exists a clump of grass. If so, help him find a certain one.

Pico the Puppy, together with FuuFuu and Kotsuki, lives in the KFP apartment. They often play a board game together called Sternhalma, commonly known as Chinese checkers. The objective of the game is to race all of one's pieces across the hexagram-shaped board to the opposite side, using single-step moves or moves that jump over other pieces.

One day, Pico wants to play Sternhalma again, but Kotsuki is out at work, and FuuFuu is still sleeping. Feeling bored, Pico intends to play on his own for a while. Pico simplifies the board into the shape shown in the picture below, with a total of $$$19$$$ grids, and he assigns a score to each grid.

Initially, he places a number of pieces on the board. Then, he moves the pieces according to the rule set by himself, selecting either of the following two types of moves for each turn:

• Remove any piece directly from the board, getting no scores.
• Remove a piece by jumping over it. Formally, for two adjacent pieces $$$A$$$ and $$$B$$$, if the symmetric position of $$$A$$$ with respect to $$$B$$$ is not out of bounds and no piece is placed there, then $$$A$$$ can jump over $$$B$$$, and $$$B$$$ is removed from the board. The total score will be increased by the score assigned to the grid where $$$B$$$ is located before being removed. (We consider two pieces adjacent if and only if the grids where the two pieces are located share an edge.)

The initial score is $$$0$$$. Pico will keep removing the pieces until there are no pieces left on the board. For different initial placements of pieces, he wants to know the maximum score he can get.

Little Q is learning programming languages. He often uses Python as it is one of the most used programming languages. However, when he codes in Python, he finds that the programs do not run very efficiently, especially when compared to C/C++. He wonders if the running efficiency of Python has any improvement with version updates, and conducts an experiment.

The algorithm used in the experiment is Monte Carlo, estimating $$$\pi$$$ by generating a large number of random points in a square. He codes this algorithm in Python and runs it with different versions of Python, logging the running time. Formally, there are a total of $$$n$$$ released versions of Python, namely 3.1, 3.2, ..., 3.$$$n$$$. The running time of the algorithm on version 3.$$$i$$$ is $$$a_i$$$ ms. Little Q is surprised to find that the running efficiency of Python does change with version iterations.

Little Q also tests the running time of this algorithm in C++, which is stably $$$k$$$ ms. Then he comes up with a funny idea: using the experimental data to predict which future version of Python will have a higher efficiency than C++. Unfortunately, he forgets how to apply the regression model, so he uses a brute prediction method:

• For a future version $$$i$$$ that $$$i \gt n$$$, $$$a_i=\max(0,2a_{i-1}-a_{i-2})$$$.

With this prediction method, please tell him the earliest version of Python that has a strictly higher efficiency than C++, i.e., find the minimum $$$i$$$ such that $$$a_i \lt k$$$.

Melon is a rabbit living on the moon who is responsible for delivering moon cakes at the Mid-Autumn Festival every year. Besides the Earth, many other planets also have a demand for mooncakes. Therefore, Melon needs to consume her fairy power to travel among different planets when delivering mooncakes.

There are $$$n$$$ planets numbered from $$$1$$$ to $$$n$$$, along with $$$m$$$ tunnels. Each tunnel undirectedly connects two planets. Each planet $$$i$$$ has a color $$$c_i$$$ and a cost $$$w_i$$$ indicating the power that Melon needs to consume to land on it.

In order to save the power for interstellar travel, Melon will use a special skill: planting cinnamon trees. Initially, no cinnamon trees are planted on any of the planets. Once Melon lands on a planet without a cinnamon tree, she will immediately plant a cinnamon tree there, but she will not plant more than one cinnamon tree on each planet. If a planet is already planted with a cinnamon tree, Melon will not consume any power when she lands on that planet again. In addition, when she is on planet $$$i$$$, she can select a planet $$$j$$$ that is planted with a cinnamon tree and is not colored $$$c_i$$$, and then remotely cut down the cinnamon tree on planet $$$j$$$ and recover $$$w_j$$$ power.

Formally, Melon can perform any one of the following actions at any time on planet $$$u$$$:

• Move to an adjacent planet $$$v$$$ that is not planted with a cinnamon tree via a tunnel, consume $$$w_v$$$ power, and plant a cinnamon tree on planet $$$v$$$.
• Move to an adjacent planet that is planted with a cinnamon tree via a tunnel, without consuming power and without planting additional trees.
• Select a planet $$$v$$$ that is planted with a cinnamon tree and is not colored $$$c_u$$$, and then remotely cut down the cinnamon tree on planet $$$v$$$ (i.e., no cinnamon tree is planted on planet $$$v$$$ thereafter) and recover $$$w_v$$$ power. Please note that this action can be performed multiple times on the same planet.

Melon's fairy power cannot be lower than $$$0$$$, so she must prepare enough power before she departs. Melon wants to know the minimum amount of power she needs to prepare for the travel from the starting planet $$$s$$$ to the terminal planet $$$t$$$. Specially, Melon needs to consume $$$w_s$$$ power and plant a cinnamon tree on the starting planet $$$s$$$.

Kotsuki the Cat, together with FuuFuu and Pico, lives in the KFP apartment. As a teacher, Kotsuki needs to go to school every day to give lessons. One day, Kotsuki gives a math lesson to some grade 2 students in primary school, covering the following topics:

• Coprime: Two integers are coprime if the only positive integer that is a divisor of both of them is $$$1$$$.
• Bitwise XOR ($$$\oplus$$$): Bitwise XOR is a binary operation that takes two integers and performs the logical exclusive OR operation on each pair of corresponding bits of their binary forms. The result in each will be $$$1$$$ if only one of the bits is $$$1$$$, but will be $$$0$$$ if both are $$$0$$$ or both are $$$1$$$. For example, $$$5\oplus3=(101)_2\oplus(011)_2=(110)_2=6$$$.

After class, Kotsuki assigns homework to the students:

• Given an integer $$$x$$$, for different intervals $$$[l, r]$$$, please calculate the number of integers $$$k$$$ within the interval satisfying $$$kx \oplus x$$$ and $$$x$$$ are coprime. Formally, please calculate $$$$$$\sum_{k=l}^r[\text{gcd}(kx \oplus x,x)=1]$$$$$$ where $$$\text{gcd}(a,b)$$$ denotes the greatest common divisor of $$$a$$$ and $$$b$$$, and $$$[\ ]$$$ denotes the Iverson bracket $$$[P]={\begin{cases}1&{\text{if }}P{\text{ is true}}\\0&{\text{otherwise}}\end{cases}}$$$. Specially, $$$\text{gcd}(0,a)=a$$$.

Can you solve this grade 2 homework?

Macaronlin the Pony is a party animal who enjoys throwing parties for his friends. One day, he invites $$$n$$$ friends to his home party. As a party expert, he prepares a lot of games for his friends, including Multiplayer Rock-paper-scissors.

Rock-paper-scissors is a well-known game around the world, in which each player simultaneously makes one of three gestures, including rock, paper, and scissors. Rock beats scissors, scissors beats paper, and paper beats rock. If both players choose the same gesture, the game is tied.

Multiplayer Rock-paper-scissors is a multiplayer version of the original game. In this game, $$$n$$$ players are lined up in a row, numbered $$$1$$$ to $$$n$$$ from left to right. Then, the host Macaronlin will choose an interval $$$[l,r]$$$ for each round, and the players in this interval will play the game in order. Specifically, player $$$l$$$ and $$$l+1$$$ play first, then $$$l+1$$$ and $$$l+2$$$, and so on, and finally $$$r-1$$$ and $$$r$$$.

Macaronlin discovers that the strategy his friends use to play the game is very simple. Initially, each player has a preferred gesture, which is one of rock, paper, and scissors. When two players play a game, they will both use their currently preferred gestures. As soon as a player loses a game, his preferred gesture will immediately change to the gesture that beat him. Otherwise, his preferred gesture will not change, including the case where two players choose the same gesture resulting in a tie.

Macaronlin is going to hold several rounds of the game. He wants to know what a certain player's currently preferred gesture is after some rounds. Formally, there are two types of actions:

• 1 l r: Macaronlin chooses an interval $$$[l,r]$$$, and the players in this interval will play the game in order. Specifically, player $$$l$$$ and $$$l+1$$$ play first, then $$$l+1$$$ and $$$l+2$$$, and so on, and finally $$$r-1$$$ and $$$r$$$.
• 2 x: Macaronlin wants to know the currently preferred gesture of the player numbered $$$x$$$.

Please tell Macaronlin the answer for each action of the second type.

Adonis the Dragon is a great leader of the dragon kingdom. It is an important mission for the dragons to pass on the dragon bloodline. Therefore, Adonis decides to choose a special day each year for egg production. Today is the day!

It is not easy to produce a dragon egg, which needs to collect various kinds of essences such as earth, water, wind, fire, etc. Specifically, the production of a dragon egg requires $$$n$$$ kinds of essences, the amount for the $$$i$$$-th of which is $$$a_i$$$.

To improve efficiency, Adonis employs many worker dragons to collect different kinds of essences for him. There are $$$k$$$ different levels of worker dragons, from level $$$1$$$ to level $$$k$$$. The amount of essence that a worker dragon of level $$$i$$$ can obtain in one day is $$$2^{i-1}$$$, but each worker dragon can collect only one kind of essence. Adonis can assign which kind of essence each worker dragon should collect at the beginning, but it cannot be changed once assigned.

Knowing that the number of dragons of level $$$i$$$ is $$$b_i$$$, Adonis wants to know the maximum number of dragon eggs that can be produced today with the best assignment.

FuuFuu the Panda, together with Pico and Kotsuki, lives in the KFP apartment. As a rare species, FuuFuu is well-treated. Therefore, his daily activities are only eating and sleeping.

One afternoon, Kotsuki is still working outside, and FuuFuu has finished his lunch and intends to go to sleep. But Pico feels too bored to play alone every day and wants to play a game with FuuFuu for a while. Although not very reluctant, FuuFuu agrees.

Pico picks $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$, and sets $$$k$$$ constraints, the $$$i$$$-th of which is $$$\text{limit}_{x_i}=y_i$$$, indicating that the maximum number of occurrences of $$$x_i$$$ is $$$y_i$$$. Then Pico and FuuFuu take turns playing the game, where each player can choose a positive integer among $$$a_1, a_2, \dots a_n$$$ for each turn and reduce it by $$$1$$$. A player will lose the game if he cannot perform any action on his turn, where there are two cases:

• No matter which of $$$a_1, a_2, \dots a_n$$$ is chosen, there exists an integer $$$x$$$ whose number of occurrences will be strictly greater than $$$\text{limit}_x$$$.
• $$$a_1=a_2=\dots=a_n=0$$$.

Even though FuuFuu is sleepy, he does not want to lose the game. Please tell him who will win if Pico goes first and both of them play optimally.

Redcrown the Bear is a gamer who likes playing hardcore games such as I Wanna series. As an experienced player, he has also made many I Wanna levels by himself.

Redcrown is making a new level with a puzzle: given $$$\tilde{k},\tilde{x}$$$ and several consecutive positive integers from $$$l$$$ to $$$r$$$, the player needs to determine whether there exist $$$\tilde{k}$$$ different integers such that their sum is $$$\tilde{x}$$$. Now Redcrown needs to decide the range of the given integers in this level, denoted by the interval $$$[l,r]$$$. In addition to $$$0 \lt l \le r$$$, he wants to make the interval satisfy $$$n$$$ conditions, each of which is of one of the following two types:

• 1 k x: there exist $$$k$$$ different integers within the interval $$$[l,r]$$$ such that their sum is $$$x$$$.
• 2 k x: there do not exist $$$k$$$ different integers within the interval $$$[l,r]$$$ such that their sum is $$$x$$$. (There are two possible cases: there are less than $$$k$$$ integers in this interval; or, there are $$$k$$$ or more integers in this interval, but there are no $$$k$$$ integers whose sum is $$$x$$$.)

Redcrown wants to know the number of different intervals $$$[l,r]$$$ that satisfy the conditions.

HoshiYo the Fox is a magician who is new to the magic school. As a novice, he is not proficient in many kinds of magic, especially those about numbers.

One day, HoshiYo learns a kind of magic that can change the integers in an array of length $$$2^n$$$. However, due to a lack of proficiency, he can only change half of the integers in the array each time he uses magic. Formally, let's denote the array as $$$a_0, a_1, \dots, a_{2^n-1}$$$, the following action can be performed by using the magic once:

• Choose $$$2^{n-1}$$$ different integers in the array and an integer $$$x$$$ (possibly negative), add $$$x$$$ to one of them, add $$$x+2$$$ to another one of them, add $$$x+4$$$ to another one of them, ..., and add $$$x+2^n-2$$$ to the last remaining one. In other words, choose $$$2^{n-1}$$$ different indices ranging from $$$0$$$ to $$$2^n-1$$$ denoted by $$$p_0,p_1,\dots,p_{2^{n-1}-1}$$$, and add $$$x+2i$$$ to $$$a_{p_i}$$$ for each integer $$$i$$$ within $$$0 \le i \lt 2^{n-1}$$$.

Initially, each integer in the array is $$$0$$$. HoshiYo has an ideal array $$$b_0, b_1, \dots, b_{2^n-1}$$$ in his mind. He wonders if he can get this ideal array by using magic at most $$$2^n$$$ times, i.e., to make $$$a_0=b_0,a_1=b_1,\dots,a_{2^n-1}=b_{2^n-1}$$$.

Rousong the Fox is a string master who can handle a wide variety of strings with ease. For example, he can braid noodles with his tongue. Likewise, he is good with string data types in computer programming.

One night, Rousong has a dream, in which he picks an infinitely long string out of the bowl when eating noodles. On closer inspection, it is a binary string containing only zeros and ones, concatenated by $$$0,1,10,11,\dots$$$. Formally, let's define string $$$s^0=0$$$, and $$$s^i=s^{i-1}+(i)_2$$$ for each integer $$$i \gt 0$$$, where $$$a+b$$$ denotes the concatenation of string $$$a$$$ and $$$b$$$, and $$$(i)_2$$$ denotes the binary form of integer $$$i$$$ without leading zeros. Consequently, the infinitely long string Rousong dreamed of is $$$s^\infty=011011100101\dots$$$.

Since the length of $$$s^\infty$$$ is too large, Rousong only wants to focus on the substring from the $$$l$$$-th character to the $$$r$$$-th character, denoted as $$$s^\infty_{l,r}$$$. He wants to find the substring of length $$$n$$$ within the string $$$s^\infty_{l,r}$$$ with the largest lexicographical order. Formally, please find the index $$$i$$$ within $$$l \le i \le r-n+1$$$ that maximizes the lexicographical order of $$$s^\infty_{i,i+n-1}$$$. Can you help Rousong solve this problem before he wakes up?

For two binary strings of the same length $$$a$$$ and $$$b$$$, we say that string $$$a$$$ is lexicographically greater than string $$$b$$$ if for the first index $$$i$$$ where $$$a$$$ and $$$b$$$ differ, the $$$i$$$-th character of $$$a$$$ is $$$1$$$ and of $$$b$$$ is $$$0$$$.