Two players are competing in a two-player game involving $$$n$$$ decks of cards. The $$$i$$$-th deck contains $$$p_i$$$ red cards and $$$q_i$$$ blue cards. The cards in each deck are indistinguishable from one another when placed face down.

The game consists of $$$n$$$ rounds, with each round played as follows:

1. At the beginning of each round, one player is assigned the role of the dealer and the other the role of the guesser.
2. The dealer chooses one of the remaining decks and shuffles the cards, placing them face down on the table.
3. The guesser selects one card from the deck and flips it over:
   • If the card is red, the roles remain the same for the next round.
   • If the card is blue, the roles are switched for the next round, with the dealer becoming the guesser and the guesser becoming the dealer.
4. Once a deck is used in a round, it is discarded and cannot be chosen again.

Given that both players are playing optimally and know the exact composition of each deck (i.e., the number of red and blue cards in each deck), determine the probability that the player who starts as the dealer will win the game.

Let $$$P = 1\,000\,000\,007$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ where $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0 \pmod P$$$. Output the integer equal to $$$x\cdot y^{-1} \pmod P$$$. In other words, output such an integer $$$a$$$ that $$$0 \le a \lt P$$$ and $$$a\cdot y=x \pmod P$$$.

In the fairy village with a river passing through the middle of the city, there is a fairy named Emma who wishes to fly higher into the sky. In order for that, she decides to borrow the power of pixie dusts, however; pixie dusts aren't for sale. So she has to make it herself by mixing the elements that she gets from the shop. In the shop, there are $$$M$$$ elements, and each of them has the cuteness level of $$$A[i]$$$. Each element has a $$$\textbf{distinct}$$$ cuteness level from others. However, Emma is allowed to purchase only $$$N$$$ elements (any elements).

Making pixie dust isn't an easy task. To make it, two elements have to be combined. Assuming those have cuteness levels of $$$X$$$ and $$$Y$$$, the result will be $$$\textbf{one}$$$ pixie dust and an element of cuteness level of $$$GCD(X, Y)$$$. (Note that this result element can be used to create another pixie dust again and again and those 2 initial elements will be $$$\textbf{gone}$$$)

Emma's goal is to get $$$K$$$ pixie dust to fly through the mist and cloud, together with maximizing the sum of the cuteness levels of every element left. Emma will be very pleased if you help her choose $$$N$$$ elements from the shop and tell her the maximum sum of the cuteness levels of every element left.

There are $$$N$$$ pairs of chopsticks. The length of each chopstick of the $$$i^{th}$$$ pair is $$$l_i$$$ unit. Each chopstick is so thin that you can consider it as a line segment. Find the maximum area of the rectangle you can form by selecting two pairs of chopsticks.

You are the manager of the animal circus show. You have $$$N$$$ types of animals in your storage; you have $$$a_i$$$ animals of $$$i^{th}$$$ type. You have to group the animals into a cage such that each cage has exactly $$$k$$$ animals, and for some reason, having the same type of animal in one cage is kind of boring for the visitors, so you should never put the same type of animal in the same cage. The problem is that the animal circus show lasts for $$$Q$$$ days, and on the $$$i^{th}$$$ day, the animal of type $$$x_i$$$ got changed by $$$y_i$$$ (if $$$y_i$$$ is positive, the number of animals of type $$$x_i$$$ increases by $$$y_i$$$, otherwise, the number of animals of type $$$x_i$$$ decreases by $$$-y_i$$$)

Your job is to find the maximum number of cages you can bring to the show each day.

In this problem, the last answer will affect the next question by equation $$$ x_{new} = (answer \oplus x_{i}) \%\ N + 1 $$$ where $$$x_{new}$$$ is the $$$x$$$ of the next question, $$$answer$$$ is the latest output, and $$$x_i$$$ is the new input.

where $$$\oplus$$$ representing Bitwise XOR

and $$$\%$$$ representing Modulo

There are $$$N$$$ days. Your normal income is $$$a$$$ baht per day. There are some hidden projects, of which you can conduct as many as you want.

To conduct a project, the rules are as follows:

$$$\scriptsize{\bullet}$$$ Choose integers $$$l$$$, $$$r$$$ such that $$$1 \leq l \leq r \leq N$$$ which represent the days the project starts and finishes, respectively.

$$$\scriptsize{\bullet}$$$ On the $$$i^{th}$$$ day, $$$l \leq i \leq r$$$, you will receive $$$i-l+1$$$ baht.

$$$\scriptsize{\bullet}$$$ You will not receive your normal income on the day between $$$l^{th}$$$ and $$$r^{th}$$$, inclusive.

$$$\scriptsize{\bullet}$$$ There must not be any days more than one project is conducted. For a little clarity, you cannot start a project on the same day you finish another project.

Please find the maximum amount of money that can be earned in $$$N$$$ days.

In a galaxy far, far away, humanity has successfully established civilization across multiple planets within a star system. This system, which contains $$$n$$$ planets, is connected by a network of $$$n-1$$$ portals. These portals enable swift and efficient travel between the planets, ensuring that every planet is accessible from any other. The technology that powers these portals is sophisticated and advanced, but like all technology, it requires maintenance and upgrades to keep functioning optimally.

Isaac, a skilled electrician known for his expertise in portal technology, is tasked with a crucial mission. The central administration unit has decided that it's time to upgrade the firmware of all the portals in the star system to improve their performance and security. To accomplish this, all the portals need to be disabled temporarily first, which is precisely his mission.

Before disabling a portal, Isaac must first test its functionality by traveling through it at least once. But to avoid the risk of forgetting to disable any portal, Isaac decides that once he travels through a portal, he will immediately disable that portal. And since a disabled portal cannot be used for traveling, it means that he can only use each portal once. This creates a problem: how can he disable all the portals and still return back? The more he thinks about it, the more he realizes that it's impossible to achieve this without some form of intervention.

Fortunately, Isaac has a powerful tool at his disposal: a jammer. This device allows him to travel through portals even after they've been disabled. However, the jammer comes with a significant cost. Each time Isaac activates the jammer, it costs $$$c$$$, and for every portal he travels through while the jammer is activated, it costs $$$w_i$$$ to travel through the $$$i$$$-th portal (even if the portal is not disabled). Importantly, while the jammer is active, Isaac cannot disable any portals, meaning he must deactivate the jammer before he can continue disabling portals. Moreover, Isaac can only activate the jammer a limited number of times — at most $$$\frac{n}{2}$$$ times.

You are tasked to help Isaac find the minimum possible cost to disable all the portals, starting and ending at planet $$$1$$$. Additionally, you need to identify the optimal planets where he should activate and deactivate the jammer to achieve this goal.

One evening, Jack decides to ride his elephant in a straight line to catch grasshoppers. His elephant is $$$H$$$ units tall.

There are $$$N$$$ grasshoppers in his path. He will encounter the $$$i^{th}$$$ grasshopper when his elephant runs for $$$x_i$$$ units, and its altitude will be $$$y_i$$$ units. He also has $$$M$$$ miracle nets for catching insects. The $$$j^{th}$$$ net is $$$l_j$$$ units long.

He will be able to catch the $$$i^{th}$$$ grasshopper with the $$$j^{th}$$$ net if and only if his elephant runs for $$$\textbf{exactly}$$$ $$$x_i$$$ units and $$$ H - l_j \leq y_i \leq H + l_j$$$. Each net will $$$\textbf{disappear}$$$ when he $$$\textbf{catch a grasshopper with it}$$$ (exchanging for transporting the grasshopper to his kitchen).

Jack has $$$Q$$$ questions for you. For the $$$i^{th}$$$ question, Jack wants to know if he wants to catch $$$q_i$$$ grasshoppers, what is the minimum distance he will have to travel.

Professor H is planning out a quiz for his subject. He wants to create $$$n$$$ multiple-choice questions, each with $$$k$$$ possible options.

At first, the professor desires to make a quiz such that all the problems have the same answer. However, the university has stated a regulation that all quizzes cannot contain any instance of four consecutive problems with the same answer. Formally, let $$$a_i$$$ be the answer of the $$$i$$$-th question in the quiz. For all $$$i$$$ from $$$1$$$ to $$$n-3$$$, if $$$a_i = a_{i+1} = a_{i+2}$$$, then $$$a_{i+3} \neq a_i$$$.

Still, the professor wants to follow his original idea. So instead, he aims to maximize the instances where three consecutive problems have the same answer.

You have been tasked to find out how many quizzes the professor can come up with. Two quizzes are different if there exists a problem that has different answer.

This is an interactive problem.

"You'll see more with your eyes closed" — Lulu

On Lulu's birthday, Pix comes up with a great present, a magical integer array $$$A$$$ of length $$$n$$$. The number of this array cannot be seen by eyes, but Lulu can cast a magical query asking for the bitwise XOR of 2 distinct elements of the array. More formally, Lulu can ask for the value of $$$A[i] \oplus A[j] (i\neq j)$$$ where $$$\oplus$$$ denotes the bitwise XOR operator. (You can find more details about the bitwise XOR operator in the notes.)

With her eyes closed, Lulu is certain that she can tell the minimum of the bitwise XOR between any 2 distinct elements of the array $$$A$$$ by casting no more than $$$n$$$ magical queries.

More formally, Lulu needs to find $$$min_{1 \leq i,j \leq n, i\ne j} A[i] \oplus A[j]$$$

Please help Lulu find this number!

You are given a chessboard of size $$$r \cdot c$$$ and a sequence of $$$q$$$ queries.

Each query consists of two integers $$$x$$$ and $$$y$$$, representing the coordinates of a cell on the chessboard. For each query:

• If the cell ((x, y)) is empty, place a pawn in that cell.
• If the cell ((x, y)) already contains a pawn, remove the pawn from that cell.

After executing each query, report the number of cells on the chessboard where a rook can be placed such that it can attack exactly one pawn. A rook can attack a pawn if they are in the same row or column and there is no other pawn between them. The rook cannot be placed in a cell that already contains a pawn.

For example, in the image above, the rook placing at $$$(6,3)$$$ can attack the pawn at $$$(2,3)$$$ and $$$(6,5)$$$ but not the one at $$$(6,8)$$$ because there is a pawn between them.

In another world, aside from luck, there are $$$K$$$ types of stat for each adventurer.

In that world, there is a shop run by an archwizard lady and a masked man. The shop is likely going to go bankrupt in the near future because the archwizard always purchases useless stuff as an investment. However, she is certain that the investment this time will surely return profit, with buff potions!

The shop plans to sell $$$N$$$ kinds of potions. The $$$i^{th}$$$ kind potion buffs $$$n_i$$$ types of stat: $$$t_1,t_2,\dots,t_{n_i}$$$ and costs $$$c_i$$$ units. When the $$$i^{th}$$$ kind potion is consumed, if the consumer is lucky, each stat type of all $$$n_i$$$ types will be maximized, or else, if they are not lucky enough, the consumer will not get any buff and will have diarrhea instead. The effect lasts one day for both cases. Different kinds of potions can be consumed together. The shop stocks each kind of potion abundantly such that it is guaranteed that there is no kind of potion that will run out of stock.

A certain adventurer with extreme luck makes a plan to buy potions because he suffers too much headache from his party in each and every mission. "Last mission, my archpriest's healing almost killed me. My archwizard blows up everything — including the money from the mission. And my crusader...she was too busy enjoying the pain." — he facepalms while writing the plan.

With his luck, he knows that every potion he consumes will definitely be effective. There are currently $$$M$$$ days in his plan. On the $$$i^{th}$$$ day, he wants to maximize $$$m_i$$$ types of stat: $$$w_1,w_2,\dots,w_{m_i}$$$. He doesn't care if the potions buff other stat types that are not listed. He wants to know the minimum cost of potions he needs to buy to achieve that goal.