Geopelia and Gino are best friends and can always read each other's minds.

One day, Gino went out early and left a note, which was found by Geopelia later.

"You have forgotten something — the yesterday...Oh, I am hungry..."

Geopelia guessed his intention at once. But she still wants to challenge you:

If you are told what day of the week it is today, answer what day of the week it was yesterday.

You are playing a computer game. To pass the current level, you need to kill all monsters solo.

As a Player, your power is quantified in two properties $$$A$$$ and $$$B$$$.

In this level, there are $$$n$$$ monsters. The $$$i$$$-th monster has two properties $$$a_i$$$ and $$$b_i$$$. To kill the $$$i$$$-th monster, you need more power correspondingly, i.e. $$$A \geq a_i$$$ and $$$B \geq b_i$$$.

Note that different monsters can have the same properties.

The Designer limits your initial properties and gives you ways below to promote them.

Initially, your properties are $$$A=10, B=10$$$. If you killed the $$$i$$$-th monster, you'll get exactly $$$c_i$$$ distributable points. Each point can promote exactly one property by $$$1$$$ forever, i.e. $$$A := A + 1$$$ or $$$B := B + 1$$$. You can use these points at any time, but each point can be used only once.

Now you can kill the monsters in any order, determine whether you can kill them all.

Feeling a little bored, WX decided to play a game called "Chain Reaction".

The game is based on a classic question "Toggle Lamps". There are $$$n$$$ lamps in total. Initially, all of them are turned off.

Also, there are $$$n$$$ buttons. If you push the $$$i$$$-th button, then all lamps $$$x$$$ such that $$$x$$$ is a multiple of $$$i$$$ will be toggled.

You have to push some button according to the following rules:

1. You need to push at least one button;
2. A button can be pushed only once;
3. You are given $$$m$$$ pairs $$$(u_i, v_i)$$$, if you push the button $$$u_i$$$, then you have to push the button $$$v_i$$$ (at any moment, not necessarily after pushing the button $$$u_i$$$). Note that if you push the button $$$v_i$$$, then you don't have to push the button $$$u_i$$$ for the given pair $$$(u_i, v_i)$$$.

Find a way to push buttons such that at most $$$\lfloor \sqrt{n} \rfloor$$$ lamps$$$^{\dagger}$$$ are on, or print $$$-1$$$ if it is impossible.

$$$^{\dagger}$$$ $$$\lfloor x \rfloor$$$ denotes the round down operation.

OP, a senior high school student, had fallen in love with the bitwise XOR operation.

So is there anything that can be done for OP? Don't worry, CY has a wonderful idea.

CY gives OP an array $$$a$$$ consisting of exactly $$$n$$$ numbers and a non-negative integer $$$k$$$. And then, CY throws him a question:

How many pairs $$$(i,j)$$$ $$$(1 \leq i \lt j \leq n)$$$ satisfy $$$a_i \oplus a_j = k$$$? Here $$$\oplus$$$ denotes the bitwise XOR operation$$$^{\dagger}$$$.

$$$^{\dagger}$$$ Bitwise XOR operation is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is $$$\mathtt{1}$$$ if only one of the bits is $$$\mathtt{1}$$$, but will be $$$\mathtt{0}$$$ if both are $$$\mathtt{0}$$$ or both are $$$\mathtt{1}$$$. In this, we perform the comparison of two bits, being $$$\mathtt{1}$$$ if the two bits are different, and $$$\mathtt{0}$$$ if they are the same. For example:

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

This is an interactive problem.

One day, you wake up to find Miku in front of you. Instead of singing, she wants to play a game with you!

This game is played on a tree with $$$n$$$ nodes, which is rooted at node $$$1$$$. A tree is a connected graph without cycles.

Miku has hidden a fufu at node $$$x$$$. You need to ask Miku the following two types of queries to find the location of it:

• $$$1~u$$$ $$$(1 \le u \le n)$$$. Miku will tell you the distance between node $$$u$$$ and node $$$x$$$. Here, the distance between two nodes denotes the number of edges in the shortest path between them.
• $$$2~v$$$ $$$(1 \le v \le n)$$$. Miku will tell you the second node on the shortest path from node $$$v$$$ to node $$$x$$$. However, when executing this query, you need to ensure that $$$v$$$ is an ancestor of $$$x$$$$$$^{\dagger}$$$, or you will immediately receive a Wrong Answer verdict due to Miku's unhappiness.

$$$^{\dagger}$$$ Node $$$a$$$ is an ancestor of node $$$b$$$ if and only if $$$a\neq b$$$, and the shortest path from node $$$1$$$ to node $$$b$$$ passes through $$$a$$$. Note that in this problem, node $$$a$$$ is not an ancestor of $$$a$$$ itself.

Can you find $$$x$$$ within $$$39$$$ queries? If you do, Miku will give you a fufu as a reward!

To make a query, you can output one of the following two formats:

• $$$1~u$$$ ($$$1 \le u \le n$$$), or
• $$$2~v$$$ ($$$1 \le v \le n$$$).

After making a query, you should read the corresponding response, which represents the distance from $$$u$$$ to $$$x$$$ or the second node on the path from $$$v$$$ to $$$x$$$, depending on your query.

If the response you read is $$$-1$$$, it means that you may have exceeded the number of allowed queries, made an invalid query, or violated the restriction for the second type of query. In this case, you should immediately exit the program and receive a Wrong Answer verdict; otherwise, you may receive a random verdict other than Accepted.

After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get Runtime Error. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• stdout.flush() in Python.

To print the answer, please output "! x" (Without quotes). Note that giving this answer is not counted towards the limit of $$$39$$$ queries.

RN is playing a music game called "Mu5Ed4sH" on her computer.

Hold is a type of note with a time range $$$[l_i, r_i]$$$, and you need to keep one finger on it within the time range.

To simplify the statement, let's assume that Hold is the only type of note in the game.

In this game, the notes will appear on two tracks, forming two sequences of time ranges $$$s$$$ and $$$t$$$. If two Holds appear at the same time, then you need to use two fingers together.

However, if you use two fingers together for $$$t$$$ seconds, then you will lose exactly $$$t$$$ energy.

Given the initial energy $$$E$$$ you have, determine whether the energy is enough to play the entire game. If it is enough, output the energy you will have left.

TN was gifted a tree of $$$n$$$ vertices with the root in the vertex $$$1$$$. A tree is a connected undirected graph without cycles.

Initially, the root has already been colored, and he wanted to color all the vertices using the operation below.

During one operation, TN can choose one uncolored vertex whose parent has already been colored and color it.

It can be shown that after $$$n-1$$$ operations, all the vertices will be colored.

Let $$$p_i$$$ be the chosen vertex of the $$$i$$$-th operation. If TN can color all vertices in this way, then the array $$$p$$$ is called Valid.

Count the number of different Valid arrays modulo $$$998244353$$$.

A shadow falls, bringing the end to the entire world. To struggle for survival, people decided to seek allies.

There are $$$n$$$ people standing in a row, who are initially unfamiliar with each other.

Also, there are $$$d$$$ conditions, the $$$i$$$-th of them restricting that $$$p_i$$$ is familiar with $$$q_i$$$.

Now, it's your decision time. Let's define that:

Your one operation is to choose two integers $$$i, j$$$ $$$(1 \leq i, j \leq n, i \neq j)$$$, such that the $$$i$$$-th person and the $$$j$$$-th person were not familiar before, and make them familiar.

Note that if $$$a$$$ is familiar with $$$b$$$ and $$$b$$$ is familiar with $$$c$$$, then $$$a$$$ is familiar with $$$c$$$.

At time $$$i$$$ $$$(1 \leq i \leq d)$$$, you can do at most $$$i$$$ operations, but you need to satisfy the conditions from $$$1$$$ to $$$i$$$ (inclusive). After the last operation of each time $$$i$$$, you need to calculate the maximal number of people that one person can be familiar with.

Note that the operations of each $$$i$$$ are independent. It means that before you start your first operation at each time $$$i$$$, you need to assume that the $$$n$$$ people are unfamiliar with each other.

On a day that could not be more ordinary, KP unexpectedly received an anonymous birthday gift — an aeroplane chess!

The gift evoked memories of his childhood, but after several hours of playing, he had a doubt:

During the Home Zone Backtrack, if the chess is on the $$$i$$$-th cell, what is the expected number of rolls required to reach the end?

Formally, assume that the chess is placed on an axis, where the point $$$\mathtt{0}$$$ denotes the end.

During one operation, you will randomly choose a number $$$y$$$ $$$(1 \leq y \leq n)$$$. Assume that the point of the chess is $$$x$$$:

• if $$$y \lt x$$$, then $$$x := x - y$$$;
• if $$$y \gt x$$$, then $$$x:= y - x$$$;
• Otherwise, the game ends.

Now you need to process $$$q$$$ queries, each query consists of a single integer $$$x$$$, denoting the point of the chess.

For each query, you need to output the expected number of operations needed to reach the end of the game.

It can be shown that the answer can be represented as $$$P / Q$$$, where $$$P$$$, $$$Q$$$ are coprime integers and $$$Q \not \equiv 0 \pmod {998244353}$$$. Print the value of $$$P \times Q^{-1} \pmod {998244353}$$$.

$$$2^k$$$ teams participate in a special tournament called Shifting Tournament.

The process of Shifting Tournament is the same as the standard tournament, which consists of $$$2^k - 1$$$ games. They are held as follows:

During the first round, all teams are split into pairs: team $$$1$$$ against team $$$2$$$, team $$$3$$$ against team $$$4$$$ (exactly in this order), and so on. Within the $$$2 ^ {k - 1}$$$ games, a team who loses the game will be eliminated, and it's guaranteed that each game results in elimination of one team (no ties). After that, $$$2 ^ {k - 1}$$$ teams remain.

During the second round, the remaining team continues according to the rules above. That means $$$2 ^{k - 2}$$$ games will take place, and $$$2^{k - 2}$$$ teams remain.

During the third round, ...

This process repeats until only one team remains, and the team is declared the champion. It's clear that there are $$$k$$$ rounds exactly.

For example, the picture below describes the chronological order of games with$$$~k=3$$$.

visual picture of $$$k = 3$$$

The specialty of the tournament is the elimination method.

Let the string $$$s$$$ consisting of $$$k$$$ characters describe the elimination method in each round as follows:

• if $$$s_i$$$ is $$$\mathtt{0}$$$, then during the $$$i$$$-th round, the team with lower index will be eliminated;
• if $$$s_i$$$ is $$$\mathtt{1}$$$, then during the $$$i$$$-th round, the team with higher index will be eliminated;
• if $$$s_i$$$ is $$$\mathtt{?}$$$, then during the $$$i$$$-th round, the team with lower or higher index will be eliminated.

Note that during the same round, the elimination method is the same.

Let $$$F(s)$$$ be the number of possible winners described by the string $$$s$$$. A team $$$i$$$ is a possible winner of the tournament if it is possible to replace every $$$\mathtt{?}$$$ with either $$$0$$$ or $$$1$$$ in such a way that team $$$i$$$ is the champion.

You are given the initial state of the string $$$s$$$, and you need to process $$$q$$$ queries:

• $$$p~c$$$ — replace $$$s_p$$$ with character $$$c$$$, and print $$$F(s)$$$ as the result of the query.

Since the answer can be huge, print it modulo $$$998244353$$$.

OC likes the stars in the sky, which are scattered but are arranged in a certain pattern.

One day, OC encounters a map with $$$n$$$ points. The $$$i$$$-th point is located at $$$(x_i, y_i)$$$.

Just like the sky, he wants to make some partitions on it. But he is too busy, so he asks you for help.

Firstly, he chooses a lucky number $$$k$$$, which will be given to you.

Then, you need to draw $$$k$$$ vertical lines and $$$k$$$ horizontal lines, meeting with the following condition:

1. Assume that the $$$i$$$-th vertical line is $$$x=a_i$$$, the $$$j$$$-th horizontal line is $$$y=b_j$$$;
2. For all $$$(x_i, y_i)$$$, $$$1 \leq i \leq n$$$, such that $$$x_i \notin a$$$ and $$$y_i \notin b$$$ (In other words, all the lines don't go through the points in the map);
3. The map is divided into $$$(k + 1) ^ 2$$$ regions by these lines. The number of points in each region is the same;
4. $$$a_i$$$ and $$$b_i$$$ can be non-integers.

HC sends you a link to an urgent file. The file is too large to download it singly, so you decide to download it in chunks.

Assume that the file is divided into $$$n$$$ chunks. For the $$$i$$$-th chunk, it will be successfully connected at moment $$$p_i$$$, then it will take exactly $$$t_i$$$ seconds to download.

Determine the moment $$$P$$$ when all chunks are successfully connected and the moment $$$F$$$ when all chunks finish downloading.