"Remember when I pulled up and said get in the car, and then cancelled my plans just in case you'd call, back when I was living for the hope of it all."

After death by a thousand cuts, he found his love. He has two parameter $$$a$$$ and $$$b$$$, and he wants to show his lover a piece of drawing bounded by the following math curves.

$$$$$$ \begin{cases} y = \sqrt{a^2 - (x-a)^2} \\ y = \sqrt{a^2 - (x+a)^2} \\ y = \frac{2b}{\pi} \left( \arccos \left(\frac{x+a}{a}\right) - \pi \right) \\ y = \frac{2b}{\pi} \left( \arcsin \left(\frac{x-a}{a}\right) - \frac{\pi}{2} \right) \end{cases} $$$$$$

Now his lover wants to know the area bounded by the close curve. Can you tell him?

Little Y lost the racing game and signed his name on the contract. He has to pay for $$$n$$$ bills! And the $$$i$$$-th bill is of $$$a_i$$$ dollars.

However, the owner of contract was devil. The owner rolled eyes and gave him a random number generator with given random seeds denoted by two integers $$$k_1$$$ and $$$k_2$$$ to get the sequence of $$$a_i$$$. The following code in C++ tells you how to generate the sequence. You can use the code directly in your submissions.

unsigned long long k1, k2;

unsigned long long xorShift128Plus() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

int n;
long long a[1000001];

void gen() {
    scanf("%d %llu %llu", &n, &k1, &k2);
    for (int i = 1; i <= n; i++) {
        a[i] = xorShift128Plus() % 999999999999 + 1;
    }
}

$$$Q$$$ commands are sent from the owner. There are four types of commands.

• $$$\texttt{F} ~ x$$$: Query the smallest unpaid bill $$$a_i$$$ where $$$a_i \ge x$$$ holds. If such $$$a_i$$$ doesn't exist, print $$$10^{12}$$$.
• $$$\texttt{D} ~ x$$$: Pay the smallest unpaid bill $$$a_i$$$ where $$$a_i \ge x$$$ holds. If such $$$a_i$$$ doesn't exist, do nothing.
• $$$\texttt{C} ~ x$$$: Query the summation of all unpaid bills $$$a_i$$$ where $$$a_i \le x$$$ holds. If such $$$a_i$$$ doesn't exist, print $$$0$$$.
• $$$\texttt{R} ~ x$$$: Refund (退款) all paid bills $$$a_i$$$ and mark them unpaid where $$$a_i \le x$$$ holds. If such $$$a_i$$$ doesn't exist, do nothing.

You are required to process these commands now.

"We bless the rain on Cornelia Street, memorize the creaks in the floor."

Creak, creak, creak... The drum beats regularly. To keep the number of syllables in harmony, one sentence in chorus is as long as one in verse. However, drumbeats in the chorus is much stronger.

Jessica wants to memorize the music, piano and drumbeat. She records the music and encodes it into a string. So, the recorded string is so strange.

Let $$$A$$$ be the pattern of verse and $$$B$$$ be the pattern of chorus. So $$$A \neq B$$$ and $$$|A| = |B|$$$. The recorded string $$$S$$$ is in the pattern of $$$AAA \cdots A ~ BB\cdots B ~ AAAAA \cdots Aa$$$. Formally, it is formed as $$$n$$$ times repeat of $$$A$$$, $$$m$$$ times repeat of $$$B$$$, $$$k$$$ times repeat of $$$A$$$, and the broken piece $$$a$$$ at the end is one prefix of $$$A$$$. And note that $$$n, m, k \gt 0, 0 \leq |a| \lt |A|$$$.

Now Jessica wants to know the pattern of $$$A$$$ and $$$B$$$. Can you help her?

While Jonathan was doing his math homework, he found a multiple-choice question:

Given a cuboid with each edge parallel to the coordinate axis, two vertexes of which are $$$(0,0,0)$$$ and $$$(a,b,c)$$$, and a plane $$$Ax + By + Cz + D = 0$$$ which intersects the cuboid. You are asked to calculate the number of edges of the cross section. Four options are provided: A. three, B. four, C. five and D. six.

Unfortunately, the number $$$D$$$ has been covered by black ink so Jonathan didn't know what exactly it is. Therefore, $$$D$$$ could be the any real number satisfying the plane intersects the cuboid in equal probability.

Then Jonathan found some options had significantly greater probability to be the correct answer in some cases. For example, if the cuboid is $$$(0,0,0),(1,1,1)$$$ and the plane is $$$x + y + D = 0$$$, then the option B has the $$$100\%$$$ probability to be the right answer. Therefore, he wanted to know each option's probability to be the correct answer in normal cases. As the problem is too hard for him, please help him to calculate the answer.

We can prove that the probability of each option is a rational number. Let's denote it by irreducible fraction $$$Q/P$$$, you are only to print the value $$$Q\times P^{-1}$$$ mod $$$10^9+7$$$. Here $$$P^{-1}$$$ is multiplicative inverse of $$$P$$$ modulo $$$10^9+7$$$.

"But there's nothing I wouldn't do to wake up and remember it."

Jonathan is fan of string problems. He is learning lexicographic order and suffix array these days.

String $$$x$$$ is lexicographically less than string $$$y$$$, if either $$$x$$$ is a prefix of $$$y$$$ (and $$$x \neq y$$$), or there exists such $$$i ~ (1 \leq i \leq \min(|x|, |y|))$$$, that $$$x_i \lt y_i$$$, and for any $$$j ~ (1 \leq j \lt i)$$$, $$$x_j = y_j$$$. Here $$$|a|$$$ denotes the length of the string $$$a$$$. The lexicographic comparison of strings is implemented by operator $$$\texttt{ \lt }$$$ in modern programming languages. For example, everybody is lexicographically smaller than somebody.

Let $$$\operatorname{suf} i$$$ be $$$x_i x_{i+1} \cdots x_n$$$ for string $$$x$$$ of length $$$n$$$. In suffix array problems, there are two commonly used arrays: $$$sa$$$ of length $$$n$$$ and $$$height$$$ of length $$$n-1$$$. Formally, $$$sa_i ~ (1 \leq i \leq n)$$$ is the starting position of the $$$i$$$-th lexicographically smallest suffix $$$\operatorname{suf} j$$$, which means $$$sa_i = j$$$. And $$$height_i ~ (2 \leq i \leq n)$$$ is the length of longest common prefix between $$$\operatorname{suf} sa_{i-1}$$$ and $$$\operatorname{suf} sa_i$$$. For example, the $$$sa$$$ and $$$height$$$ for remember is $$$\lbrace6,4,2,7,5,3,8,1\rbrace$$$ and $$$\lbrace0,2,1,0,1,0,1\rbrace$$$ respectively.

As we all know, Little Y is a Riddler. One day, Little Y got a string $$$S$$$ of length $$$n$$$ consisting of only lowercase letters. He used suffix-array algorithms to get the array $$$sa$$$ and $$$height$$$. He erased several numbers in $$$height$$$ and gave the two modified array to Jonathan.

Curiously, Jonathan wants to know what the string $$$S$$$ is. Please help him to figure out a possible answer. Since there may be multiple answers, you only need to print the lexicographically smallest one. It is guaranteed that the answer exists.

You are facing an endgame of Shogi.

You have only one Kin(金将). However, your opponent has $$$n$$$ Fu(步兵).

The rule of this game is as following.

If Kin is at $$$(x,y)$$$, it can move to one of the following positions in one step: $$$(x+1,y), (x+1,y+1), (x,y+1), (x-1,y+1), (x-1,y), (x,y-1)$$$.

If Fu is at $$$(x,y)$$$, it can only move to $$$(x,y-1)$$$ in one step.

Now you know the initial position of your Kin and your opponent's Fu. Each turn, you move your Kin first and then all Fu will move one step.

When you are moving Kin, you can defeat the Fu at that position. If one Fu moves one step and meets Kin, your opponent is also defeated.

To win this game, you want to defeat Fu as many as possible. Now Chino wonders the maximum count of Fu that will be defeated. Can you help cute Chino?

"Goodbye to the friends I've had, goodbye to my upstairs neighbor, goodbye to the kids downstairs, and anybody who lend me a favor."

"Or, goodbye to the positive proper divisor?"

That game is popular these days. Two player take turns to choose a specific number and claim it. The player who takes the first turn chooses one positive proper divisor of given $$$n$$$. In the next rounds, player should choose one positive proper divisor (真因数) of the number claimed in the previous round. The player who can't make a choice will win.

Formally, a positive proper divisor of $$$n$$$ is a divisor of $$$n$$$, and it cannot be either $$$1$$$ or $$$n$$$.

Now Chino is going to play this game with David. Chino always wants to win and meanwhile she wants to keep the chosen number as big as possible. If with the given $$$n$$$, Chino will win directly or fail anyway, you should also tell her.

Can you help Chino to choose her answer in the first round?

Little Y can't help himself learning number theory. However, math is too hard for him. He was beaten by SPOJ AFS3 and felt down. So here is a simple math problem.

Let $$$\sigma_k(n)$$$ be the following definition:

$$$$$$ \sigma_k(n) = \sum_{d|n} d^k $$$$$$

For example, when $$$k=0$$$, this function is known as the count of divisors of $$$n$$$. And when $$$k=1$$$, this function is known as the sum of divisors of $$$n$$$.

Now he wants to calculate the following fomula for given $$$a$$$ and $$$b$$$.

$$$$$$ \left( \left( \sum_{i=1}^n \sigma_a(i) \right) \oplus \left( \sum_{i=1}^n \sigma_b(i) \right) \right) \mod 2^{64} $$$$$$

where $$$\oplus$$$ means the bitwise exclusive or.

Recently, Jonathan is addicted to a game called InkBall FX.

The game goes on a plane coordinate system. On the first quadrant, there are some segments. The segments are all parallel to x-axis and they are pairwise disjoint. Two segments are disjoint if and only if they don't have mutual point, including the end points. Therefore, we can use $$$(L_i, R_i, Y_i)$$$ to note the $$$i^{th}$$$ segment, which means the segment starts from the position $$$(L_i, Y_i)$$$ and ends in the position $$$(R_i, Y_i)$$$.

There is an extremely small ball on the position $$$(0,0)$$$. At the beginning, the speed of the ball in the horizontal direction is $$$1$$$ per second, and that in the vertical direction is also $$$1$$$ per second. If the ball is now at the position $$$(x,y)$$$, then it will move to the position $$$(x+t,y+t)$$$ after $$$t$$$ seconds, if it does not touch the segment during this process.

When the ball hits any segment, a completely elastic collision occurs, which means the speed in vertical direction will be reversed and that in the horizontal direction will remain the same, since the segments are parallel to x-axis. After the collision, the segment will disappear, which means it cannot be collided twice.

If the ball hits the ends of the segment, the collision still occurs like what's mentioned before.

Jonathan is curious about how many segments the ball could hit, but the ball moves too slow. Please write a program to help him to get the answer quickly.

Chino has $$$n$$$ jingle bells, and she plans to decorate them on the Christmas tree one by one.

However, this Christmas tree is strange. This tree has $$$n$$$ nodes, numbered from $$$1$$$ to $$$n$$$. Each node has two value $$$a_i, b_i$$$. When Chino puts a jingle bell on node $$$i$$$, she will gain beauty value. Formally, after putting one jingle bell, let $$$S$$$ be the set of nodes which contains at least one jingle bell, she will get $$$b_i \times \sum_{j \notin S} a_j$$$ points.

At the beginning, Chino can only put bells on the root node of the Christmas tree and get $$$0$$$ points. Then Chino can put jingle bells on any node $$$v$$$ satisfying $$$(u,v) \in E(G), u \in S, v \notin S$$$ and get its beauty value.

Chino want to make Christmas tree the most beautiful, but she don't know the maximum beauty value she can get. Can you help her?

Little Y is a Riddler. He always says that this is a secret.

One day, he got a undirected tree. He met Jessica and say, "Hey! I've got a new tree. Do you want to guess? This is a secret."

"This is a tree with $$$n$$$ nodes. Each node has three restrictions and two parameters $$$d_i$$$ and $$$x_i$$$."

• The depth of node $$$i$$$ in the tree is $$$d_i$$$.
• The position of $$$i$$$ in the BFS sequence of tree should be less than or equal to $$$x_i$$$.
• If $$$x$$$ is before $$$y$$$ in BFS sequence, either the parent node of $$$x$$$ is also the parent node of $$$y$$$, or the parent node of $$$x$$$ is before the parent node of $$$y$$$ in BFS sequence.

However, Jessica quickly finds that too many trees satisfy his conditions. To give him a lesson, she wants to figure out the number of the trees satisfying all these restrictions. Can you help her?

"Don't wanna walk alone. So, let's get married."

Little Y lives in a strange town, which can be represented by a finite 2D plane. Each grid point on the 2D plane has a unique number. The unique number is generated by breadth first search. The origin point $$$(0, 0)$$$ is numbered as $$$0$$$. We search for the points which is not accessed yet (in the order of top, right, bottom, left) and number them with the smallest available positive number.

$$$$$$ \begin{matrix} & & 5 & & \\ & 7 & 1 & 6 & \\ \cdots & 4 & 0 & 2 & 8 \\ & \cdots & 3 & 9 & \\ & & \cdots & & \end{matrix} $$$$$$

For example, the point $$$(1, -1)$$$ is for $$$9$$$ and the point $$$6$$$ is at $$$(1, 1)$$$.

One day, Little Y met Little K and quickly fell in love.

Little Y wants to follow Little K's steps. Surprisingly, Little K will publish his location.

Once noticing the location, Little Y will go to that point. However, Little Y is not clever and need your help.