One day, Little Z met a towering tree on the road, which blocked his path. With no other choice, he had to figure out a way to remove the entire tree to continue forward. Little Z, being immensely strong, could shake a node of the tree continuously until it fell off, becoming a small tree, while all the leaves of the small tree would drift to the ground and disappear.

Now, Little Z wants to know how many shakes he needs to make all nodes of the tree fall to the ground. But this is too easy for him. He also finds that the tree is not very tall. So, please also tell Little Z how many ways he can achieve this with the minimum number of shakes.

Formally, there is a rooted tree containing $$$n$$$ nodes, numbered from $$$1$$$ to $$$n$$$. The root of the tree is node $$$1$$$, and the height of the tree does not exceed $$$100$$$. In each operation, Little Z can choose a node $$$u$$$, cut $$$u$$$ from its parent (if it has one) to become the root of a new tree, and then delete all leaf nodes in the tree rooted at $$$u$$$.

Now, Little Z wants to know the minimum number of operations required to delete all nodes. You also need to answer the number of ways to delete all nodes with the minimum number of operations after modulo $$$10^9+7$$$.

Two operation schemes are considered the same if and only if they have the same number of operations and the node numbers operated on in each operation are the same.

I am Fluttershy, a plain and ordinary Pegasus pony of Equestria—well, after going through countless experiences with Twilight Sparkle and other friends, maybe I'm not that ordinary.

Like today, when I returned home, what caught my eye was countless versions of myself.

Luckily, I'm not Pinkie Pie; so instead of bouncing around chattering endlessly, they just quietly looked at me and gave me a question:

Given an array of non-negative integers $$$a_i$$$ with length $$$n$$$, I may perform the following operation no more than $$$n$$$ times:

• Choose $$$i,j$$$ such that $$$1\le i,j \le n$$$, $$$0\le x\le 10^9$$$, then set $$$a_i\leftarrow a_i+x$$$ and $$$a_j \leftarrow a_j-x$$$

I must ensure that all $$$a_i$$$ remain non-negative integers after each operation, reminded by one of us.

My goal is to minimize the value of $$$a_1 \ | \ a_2 \ | \ \ldots \ | \ a_n$$$ after the operations. Here, $$$|$$$ denotes the bitwise OR operator, and $$$x \ | \ y$$$ represents the bitwise OR of two non-negative integers $$$x$$$ and $$$y$$$.

The bitwise OR operation compares two binary numbers bit by bit. In each bit position, if at least one of the bits is $$$1$$$, then the result is $$$1$$$; otherwise, it is $$$0$$$. For example, the bitwise OR result of the binary numbers $$$10 = 1010_2$$$ and $$$12 = 1100_2$$$ is $$$14 = 1110_2$$$, and the result of $$$3 = 0011_2$$$ and $$$5 = 0101_2$$$ is $$$7 = 0111_2$$$.

TreeBag enjoys participating in the contests on the famous international competitive programming website CF (ColaFries) in his dreams, and every time he can achieve a single-digit rank in his dreams. One day, he suddenly became curious about the longest increasing subsequence of the array formed by his ranks after each competition. Therefore, he came up with the following question:

Given an integer $$$x$$$, construct a string $$$s$$$ consisting only of decimal digits(i.e. 0,1,2,$$$\dots$$$,8,9) and of length not exceeding $$$10^5$$$, such that the sum of the values of all longest strictly increasing subsequences of $$$s$$$ equals $$$x$$$.

Since TreeBag is BAKA when he wakes up from his dreams, he asks you to help him solve this problem.

The value of a string composed only of decimal digits is defined as the value of the decimal number it represents. For example, the sum of all longest strictly increasing subsequences of the string 001243 is $$$0124+0123+0124+0123=494$$$.

A string $$$t$$$ is a subsequence of $$$s$$$ if and only if $$$t$$$ can be obtained by deleting several characters (possibly $$$0$$$ characters) from $$$s$$$ without changing the order of the remaining characters. For example, the subsequence of 1011101 can be 0, 1, 11111, 101, 0111, but not 000, 101010, 11100.

A string $$$t$$$ is a strictly increasing subsequence of $$$s$$$ if and only if $$$t$$$ is a subsequence of $$$s$$$ and for any $$$1\le i \lt |t|$$$ ($$$|t|$$$ represents the length of $$$t$$$), it holds that $$$t_i \lt t_{i+1}$$$. Here, characters are compared by their numeric value.

A string $$$t$$$ is the longest strictly increasing subsequence of $$$s$$$ if and only if $$$t$$$ is a strictly increasing subsequence of $$$s$$$ and there is no strictly increasing subsequence of $$$s$$$ longer than $$$t$$$.

Mystia's Izakaya has held a new edition of the International Championship of Portion Consumption (ICPC). Although Mystia did not allocate spots for Whitejade House University (WHU) for destroying the venue in the previous year, the university still sent a team to participate, led by Yuyuko.

On a long table, there are $$$n$$$ seats arranged in a row, with the $$$i$$$-th seat from left to right having a dish with a portion size of $$$a_i$$$. Yuyuko starts at the $$$s$$$-th seat, and at the end of each second, she can move to any seat adjacent to her current seat (she can also choose to stay at her current seat). Any dish on a seat she reaches will be consumed by her.

Yuyuko wants to know the maximum total portion size of the dishes she can consume. You need to calculate the maximum total portion size of the dishes Yuyuko can consume if she starts from the $$$s$$$-th seat and moves for $$$t$$$ seconds, for all positive integers $$$s,t$$$ that satisfy $$$1 \le s \le n, 1 \le t \le 2n$$$.

I am Fluttershy, and I've encountered countless versions of myself. Even though they are not noisy at all, I still take them with me to search for my friends. I must figure this out.

In Cloudsdale, I found my friend, Rainbow Dash. She is a handsome Pegasus pony, completely different from me. Unfortunately, Rainbow Dash also encountered a problem. She told me:

The organization WHU (World Horse Unite) often spreads some news in the news, but unfortunately, some news, after a period of dissemination, is confirmed to be fake news. In order to save face, WHU has to spread another news to refute it.

"And they always ask me to refute it," Rainbow said loudly, "but I'm a little confused."

After organizing Rainbow's description, for simplicity, I assume that the message is transmitted on a tree with $$$n$$$ nodes and $$$n-1$$$ edges.

The fake news spread by WHU starts from node $$$r$$$ at time $$$0$$$, and spreads to neighboring nodes every unit of time. Formally, at time $$$t$$$, all nodes within distance $$$t$$$ from $$$r$$$ receive this message, that is, the set of nodes $$$V(r,t)=\{v | \mathrm{dis}(r,v)\le t\}$$$, where $$$\mathrm{dis}(u,v)$$$ denotes the number of edges of the unique simple path between two nodes $$$u$$$ and $$$v$$$ on the tree.

At time $$$t_0$$$, WHU will commission Rainbow to choose a new node $$$r'$$$ to refute the news, and every unit of time, the refutation will spread to nodes within distance no more than $$$k$$$ from the current node, i.e., the rate of refutation is $$$k$$$ times faster than that of fake news. Formally, at time $$$t$$$ ($$$t\ge t_0$$$), all nodes within distance $$$k(t-t_0)$$$ from $$$r'$$$ receive the refutation, that is, the set of nodes $$$V'(r',t)=\{v | \mathrm{dis}(r',v)\le k(t-t_0)\}$$$.

Now $$$r$$$ and $$$t_0$$$ are determined, but Rainbow is not sure where to start refuting, nor how fast to refute. Therefore, I need to answer for all $$$1\le k\le n$$$, when is the earliest time that fake news can be refuted when taking any $$$r'$$$. Formally, find the earliest time $$$t$$$ such that the refutation covers all the nodes covered by the fake news, i.e., $$$V(r,t)\subseteq V'(r',t)$$$.

This is an interactive problem.

"Oh, poor Opalescence," I sighed as I watched Fluttershies surround the white Persian cat.

Rarity is always so busy, and honestly, she probably struggles to solve my problems. She is not really adept at this kind of magic.

While she was busy making customized clothing, she even turned around and gave me a problem. Her problem can be abstracted as follows:

There is an $$$n \times n$$$ matrix of positive integers $$$a_{i,j}$$$ ($$$1 \leq a_{i,j} \leq n \times n$$$), which satisfies that for each $$$i \gt 1$$$, $$$a_{i,j} \geq a_{i-1,j}$$$; and for each $$$j \gt 1$$$, $$$a_{i,j} \geq a_{i,j-1}$$$.

You're provided with only the size $$$n$$$ of the matrix, without knowledge of its element values $$$a_{i,j}$$$. However, you can inquire whether a given position $$$a_{i,j}$$$ in the matrix is not greater than a specified integer $$$x$$$.

You need to find the $$$k$$$-th largest value in $$${a_{i,j}}$$$ using no more than $$$50000$$$ queries.

Note that $$$a_{i,j}$$$ may have identical values. The $$$k$$$-th largest value is defined as the value of the $$$k$$$-th element when sorting the $$$n \times n$$$ elements in descending order.

First, read the parameters $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq k \leq n \times n$$$) from the standard input.

Then, you can make no more than $$$50000$$$ queries. To make a query, output "? i j x"$$$\ $$$($$$1 \leq i,j \leq n$$$, $$$1 \leq x \leq n \times n$$$) on a separate line, and you should read the response from standard input. If $$$a_{i,j}\le x$$$, the standard input will return $$$1$$$, otherwise $$$0$$$.

Finally, to give your answer, output "! x"$$$\ $$$on a separate line, representing the $$$k$$$-th largest value in the matrix. The output of the answer is not counted towards the limit of $$$50000$$$ queries. After that, your program should terminate.

After outputting a query, do not forget to output end of line and flush the output. To do this:

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

It is guaranteed that the matrix remains unchanged during the interaction.

You have $$$n$$$ items of type A and $$$m$$$ items of type B. Each A item has a value of $$$a$$$ and each B item has a value of $$$b$$$.

You now need to determine a packaging solution for a certain product, which includes a certain number of item A and a certain number of item B (it is allowed to contain only item A or only item B), satisfying the total value of the items to be $$$k$$$. In this packaging solution, you aim to package as many products as possible until the remaining A and B items are not sufficient to form a complete product.

Your task is to find the minimum number of items that remain unpackaged among all possible packaging solutions.

Everyone is aware that Flandre has wings adorned with crystals. However, it is less commonly known that her wings are actually made by herself.

Flandre has been given a tree composed of $$$n$$$ crystals interconnected by $$$n-1$$$ edges. This arrangement ensures that each crystal is directly or indirectly connected to others. The beauty value of the $$$i$$$-th crystal is denoted as $$$a_i$$$.

A "wing" is defined as a sequence of arbitrary length with non-repeating elements $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le n$$$) such that for every integer $$$1 \leq i \lt k$$$, the $$$b_i$$$-th crystal and the $$$b_{i+1}$$$-th crystal is connected by a single edge within the tree. The beauty value of a wing is calculated as the square of the sum of the beauty values of all included crystals, expressed mathematically as $$$\left(\sum\limits_{i=1}^k a_{b_i}\right)^2$$$.

Flandre wants to craft some wings from the crystals in this tree, such that each crystal is contained by no more than one wing. Help her determine the maximum possible sum of the beauty values for the wings she can create.

Leading the Fluttershies, we arrived at the Sweet Apple Acres.

"Only to see her lower her body, two front hooves pressed against the ground, waist twisted, legs kicked, two powerful hind legs striking the trunk like bullets. With a muffled sound accompanied by the rustling of leaves, the entire tree's apples fell into the basket without missing a beat," whispered one of the Fluttershies.

"Fluttershy, how do you have so many?" Would I talk like that, I had only just risen to this doubt when I was interrupted by Applejack's voice coming from far away.

"There's nothing wrong with that," another Fluttershy said coolly, as the apples in Applejack's basket inexplicably flew up one by one.

Strange, why would some of me even have magic? I hurriedly helped Applejack gather the apples and stopped the actions of Fluttershies.

Formally, the act of stopping can be abstracted into the following problem:

Given a string $$$s$$$ of length $$$n$$$ consisting only of 0 and 1. I can perform the following operation any number of times: choose a substring of $$$s$$$ and a positive number $$$k$$$, then cyclically shift the substring $$$k$$$ positions to the left.

String $$$a$$$ is a substring of string $$$b$$$ if and only if $$$a$$$ can be obtained by deleting some characters from the beginning and end of $$$b$$$ (which can be none or all of them).

Assume there is a string $$$s=s_0s_1s_2\dots s_{m-2}s_{m-1}$$$, shifting it $$$k$$$ positions to the left will result in $$$s_{k'}s_{k'+1}\dots s_{m-1}s_{0}s_{1}\dots s_{k'-2}s_{k'-1}$$$, where $$$k'=k\bmod m$$$.

A string $$$s$$$ consisting only of 0 and 1 is sorted if and only if for all $$$1 \leq i \lt n$$$, $$$s_i \leq s_{i+1}$$$. Here, characters are compared based on their numerical values.

For example, shifting the substring 1011 of string 0101100 two positions to the left results in 0111000.

I need to find the minimum number of operations required to make $$$s$$$ sorted.

The Mystia's Izakaya has $$$n$$$ branches in Gensokyo, numbered from $$$1$$$ to $$$n$$$. There are $$$m$$$ one-way roads of length $$$1$$$ between these $$$n$$$ branches, with the $$$i$$$-th road leading from branch $$$u_i$$$ to branch $$$v_i$$$.

To strengthen the connections between the branches, Mystia decided to build some more roads, so she hired $$$k$$$ construction teams. For the $$$i$$$-th team, Mystia will uniformly randomly select an integer $$$j$$$ from $$$[1, m] \cap \mathbb{Z}$$$ and assign the $$$i$$$-th construction team to build $$$a_i$$$ one-way roads of length $$$1$$$ from branch $$$u_j$$$ to branch $$$v_j$$$. The integers $$$j$$$ selected for the construction teams are independent of each other.

The two largest branches of the Izakaya are branch $$$1$$$ and branch $$$n$$$. Your task is to help Mystia calculate the expected number of shortest paths from branch $$$1$$$ to branch $$$n$$$ after the road construction is completed. The answer should be modulo $$$998244353$$$.

After finally rounding up the Fluttershies at Sweet Apple Acres, we made our way to Pinkie Pie's Sugarcube Corner.

"Wheee!!! Fluttershies, let's have a party!"

There was no way around it; we had to join in and play with Pinkie Pie.

Pinkie Pie invented a two-player game, and we took turns challenging her. Specifically, the game goes as follows:

There are $$$n$$$ integers $$$1,2,3,\dots,n$$$​ arranged in a row from left to right. Both Pinkie Pie and I will take turns trying the following operation:

• If the bitwise XOR sum of the remaining integers is not $$$0$$$​, remove either the leftmost or the rightmost integer from the row without changing the order of the remaining numbers.

If the current player cannot make a move, they lose the game.

The game consists of $$$T$$$ rounds, assuming "I"$$$\ $$$always starts first each round, and both of us aim for victory by making optimal moves. The question is whether "I"$$$\ $$$can achieve victory in each round of the game.

The bitwise XOR sum of several numbers $$$a_1,a_2,\dots,a_m$$$ is denoted by $$$a_1 \oplus a_2 \oplus \dots \oplus a_m$$$. Particularly, the XOR sum of an empty set is $$$0$$$.

The XOR operation, denoted by $$$\oplus$$$, is a binary operation that compares two binary numbers bit by bit. At each position, if the corresponding bits are not all $$$1$$$ or not all $$$0$$$, the result is $$$1$$$; otherwise, it's $$$0$$$.

"Fluttershy, this really isn't Discord's trickery,"$$$\ $$$Twilight Sparkle said to me upon returning from the Canterlot Library. "It's just a group of mischievous magic fairies."

"Magic fairies?"

"They are a pure form of magical beings, capable of freely manipulating natural magic fields to construct external shells. They imitated your appearance to find you, probably just because they really like you."

"Is that so?"$$$\ $$$I glanced at the Fluttershies, and they nodded slightly before emitting a faint glow, blurring our vision.

"It's over now, now that we know all this, but they left behind a puzzle."$$$\ $$$We both watched as they gradually transformed into a group of shining butterflies.

"Let's take a look together."$$$\ $$$The butterflies drifted away in the sunlight, gradually disappearing into the play of light and shadow.

Specifically, the fairies have built $$$n$$$ rectangular pillars of width $$$1$$$ right next to each other on the numbered axes, and the height of the column at position $$$i$$$ is $$$h_i$$$.

In particular, imaginary infinite-height pillars are considered to exist in front of the first pillar and behind the last one, i.e., $$$h_0$$$ and $$$h_{n+1}$$$ are treated as infinite height. Also, no two pillars have the same height.

Next, $$$q$$$ independent queries $$$x,V$$$ are given, indicating that water falls vertically from the infinite height at position $$$x$$$, covering an area of $$$V$$$ units. We need to answer how many of the tops of the pillars were submerged by water after the water flow was complete, i.e., they were covered with water of thickness greater than $$$0$$$.

In particular, for convenience, it is guaranteed that all $$$V$$$ are even.

Water flow: Assume that the water is an ideal fluid and no atmospheric pressure here, so the water always tends to flow to somewhere strictly lower, even when the water is on a horizontal stage. In particular, if the water is on the column surface of some pillars whose height is greater on both sides, the water will equal flow to both sides. Since no two pillars have the same height, this will only happen on the surface of pillar where the water initially falls.

Siri is playing a WeChat mini-game that involves a two-player duel, so he called Dagu to play the game with him.

The game process is as follows: At the start of the game, both players are given a number of soldiers. Siri receives $$$n$$$ soldiers, the $$$i$$$-th of which with a combat power of $$$a_i$$$; Dagu also receives several soldiers. Each round, both sides summon one still-surviving soldier to fight. The side with the higher combat power will defeat the opponent's soldier and directly kill the opponent's general, winning the game. If the combat powers are equal, both soldiers die simultaneously and the next round begins. If all soldiers on both sides have fallen, the game is declared a draw.

To more easily win the game, Siri has installed a cheat that allows him to perform the following operation any number of times: merge two soldiers whose combat powers differ exactly by $$$1$$$ into a new soldier with a combat power equal to the sum of the original two soldiers' combat powers.

Clearly, in this game, sorting the sequence of each player's soldiers' combat powers in descending order, the player with the lexicographically larger sequence has a guaranteed winning strategy. Help Siri use the cheat to merge soldiers so that his sequence of soldiers' combat powers, when sorted in descending order, is lexicographically as large as possible. You only need to output the combat powers of the merged soldiers in any order.

A sequence $$$a = [a_1, a_2, \ldots, a_{|a|}]$$$ is lexicographically smaller than a sequence $$$b = [b_1, b_2, \ldots, b_{|b|}]$$$ if and only if at least one of the following is true:

• $$$a$$$ is an empty sequence and $$$b$$$ is not an empty sequence.
• Both $$$a$$$ and $$$b$$$ are not empty sequences and $$$a_1 \lt b_1$$$.
• Both $$$a$$$ and $$$b$$$ are not empty sequences and $$$a_1 = b_1$$$ and $$$[a_2, a_3, \ldots, a_{|a|}]$$$ is lexicographically smaller than $$$[b_2, b_3, \ldots, b_{|b|}]$$$.