Esomer doesn't want to go to class at university, but he needs notes from his lectures to be able to study. Therefore, he has come up with the following system.

The university can be represented as a tree of $$$n$$$ nodes, and on a single day, Esomer will have $$$k$$$ classes on consecutive hours. Additionally, Esomer will hire note-takers. A note-taker can be hired at node $$$i$$$ at any time for a cost of $$$c_i$$$. Additionally, all note-takers can move to any neighbor node of their current node between hours. Note that Esomer can hire several note-takers at the same node and at the same time, and at any point in time, several note-takers can be at the same node.

Esomer's demand is simple, for each of his $$$k$$$ classes at nodes $$$v_1, v_2, \ldots, v_k$$$, there needs to be at least one note-taker at node $$$v_i$$$ at hour $$$i$$$, so that Esomer will get the notes for the class.

Unfortunately, Esomer is not rich, so he wants to pay the least possible amount in total, and he has asked for your help in calculating that quantity.

We have a matrix with $$$n$$$ rows and $$$m$$$ columns, where all its values are initially set to $$$0$$$.

Additionally, we have $$$q$$$ operations of two types:

$$$*$$$ The first type of operation flips (changes $$$0$$$ to $$$1$$$ and $$$1$$$ to $$$0$$$) an entire row or column.

$$$*$$$ The second type of operation queries the sum of a submatrix.

The top-left corner of the matrix corresponds to position $$$(1, 1)$$$, and the bottom-right corner corresponds to position $$$(n, m)$$$.

It's your first time visiting Bratislava, and because your reputation as a good programmer precedes you, the mayor of Bratislava appoints you to solve a problem.

Bratislava has $$$n$$$ villages, but there are no roads connecting any two villages. In other words, you cannot travel from one village to another; each village is initially isolated. Building roads is expensive, so the mayor has a maximum budget that allows for constructing up to $$$m$$$ roads.

Your task is to minimize the maximum possible distance between all the villages.

We have an infinite matrix $$$A$$$ defined as: $$$A_{i,j} = i + j$$$ for all $$$i, j$$$ such that $$$0 \le i, j$$$.

An infinite matrix $$$B$$$ is defined as: $$$\forall i,j$$$ such that $$$0 \le i$$$ and $$$1 \le j$$$ we have $$$B_{i,j}$$$ $$$=$$$ $$$A_{i,j-1}$$$ $$$\oplus$$$ $$$A_{i,j}$$$ $$$\oplus$$$ $$$A_{i,j+1}$$$.

Here $$$\oplus$$$ denotes the bitwise XOR operator.

If you are unfamiliar with XOR, please make sure to check out Esomer's XOR ultimate guide.

You are now given $$$q$$$ queries of the type $$${a, b, c, d}$$$. You are asked to find the total sum of all $$$B_{i,j}$$$ such that $$$a \le i \le c$$$ and $$$b \le j \le d$$$.

Gridland is a mysterious world which exists inside of the Cartesian plane.

According to tradition, perhaps superstition, all the roads in Gridland must be made of linear segments parallel to the $$$x$$$ axis or the $$$y$$$ axis. The trains of Gridland have a very interesting property: they can only turn at most twice in one journey. This used to be an inconvenience for its citizens, who sometimes had to take more than one train in order to travel between two cities.

After a civil war broke out, the entire railway infrastructure of the country was destroyed. The new Minister of Transportation, Gustavo, has proposed an ambitious plan to build a new railway network that allows direct train travels between every city. However, Gustavo has to devise a budget to determine the project's feasibility. He needs your help to figure out the minimum total length of the new railway network.

You are given $$$l$$$ and $$$r$$$ and you are asked to calculate the number pairs $$$(a, b)$$$ in that interval interval such that $$$a \lt b$$$, $$$a \oplus b \gt b$$$ and $$$l \le a, b \le r$$$.

Here $$$\oplus$$$ denotes XOR bitwise operation.

If you are unfamiliar with XOR, please visit Esomer's XOR ultimate guide.

We are playing "Twister" with Echomel, but he is a dirty cheater, and we believe not all his limbs are inside the game panel.

You are given two pairs of integers representing the coordinates of the bottom-left and top-right corners of the Twister panel, respectively. The game panel is a rectangle.

Next, you will be given 4 pairs of integers, representing the coordinates where Echomel has placed his left hand, right hand, left foot, and right foot, respectively.

Note 1: Echomel is VERY flexible.

Guadalajara is famous for its majestic mountains in the north and its well-known coastal town, Villanueva de la Torre. The regal, grand and dignifiedis danx is visiting Hectorungo, and during his visit, he will conduct a survey about the water in the alcarrian towns.

We have $$$2n-1$$$ towns, all associated with a river, organized in a tree structure where town $$$2n-1$$$ is the root.

In each town with index $$$i$$$ $$$(1 \leq i \leq n)$$$, a river originates with color $$$i$$$. Each town with index $$$j$$$ $$$(n+1 \leq j \leq 2n-1)$$$ connects two towns with smaller indices $$$a$$$ and $$$b$$$ $$$(a, b \lt j)$$$, and the rivers from these towns merge at $$$j$$$. The river of town $$$j$$$ will contain all the colors of the rivers from towns $$$a$$$ and $$$b$$$.

Each town has a population of $$$p_i$$$ inhabitants $$$(1 \leq p_i \leq 10^9)$$$.

Dani will ask $$$q$$$ questions. In each question, he will give a number $$$r$$$ followed by $$$r$$$ distinct numbers $$$c_1, c_2, \dots, c_r$$$ $$$(1 \leq c_i \leq n)$$$, where $$$c_i$$$ denotes a color.

Your task is to determine how many inhabitants live in towns whose river contains at least one of the colors given in the query.

Litusiano was solving a problem during the prestigious CAMA competition (the best competition in the world) when he came up with the following problem:

In CAMA, all participants deserve to be happy. You are given an integer $$$n$$$ and an array of integers $$$a$$$ of length $$$n$$$. The $$$i$$$-th participant will be happy if they are in one of the first $$$a_i$$$ positions in the final ranking. Your task is to find the lexicographically smallest ranking such that all $$$n$$$ participants are happy, i.e., each participant $$$i$$$ is placed within the first $$$a_i$$$ positions of the ranking.

Lexicographical order means that, given two arrays $$$x$$$ and $$$y$$$ of the same length, $$$x$$$ is smaller than $$$y$$$ if, at the first position $$$k$$$ where they differ, $$$x_k \lt y_k$$$. For example: - $$$[1, 2, 3]$$$ is smaller than $$$[1, 3, 2]$$$ because at the second position $$$2 \lt 3$$$. - $$$[2, 1, 3]$$$ is greater than $$$[1, 3, 2]$$$ because at the first position $$$2 \gt 1$$$.

In the spirit of CAMA, where everyone should leave the competition with a smile, your task is to ensure that all participants are happy. If it's not possible to construct such a ranking, return -1.

After Héctor got his Architecture degree, he received a commission from Sheikh Artur. Since Artur is an extravagant individual, he has requested that his new house be shaped like a convex polygon with marble pillars in the countryside. He has also asked for a pillar at each vertex of the polygon, although he doesn't mind if there are extra columns inside that are not at the vertices.

However, Héctor forgot that the cottage is going to be built next to a lake with the shape of a convex polygon until after he had already placed all the marble columns, and the house he designs intersects with the lake. Obviously, he won't be able to build the cottage inside the lake, and since there's no time to redesign the building, Héctor has decided to improvise using the pillars that have already been placed. Help Héctor determine the maximum number of pillars that can be in Artur's house.

For this problem, you may consider a straight line segment or a single point as a convex polygon.

A few clarifications:

Even though some columns may not be in the water, part of the house built using them might end up inside the lake. This is not allowed.

Some of the vertices of the lake may be collinear.

We say that the house and the lake intersect only if their areas overlap. The house can be built even if its perimeter overlaps with the perimeter of the lake.

Litusiano was pooing when he came up with the following problem:

Given $$$l$$$ and $$$r$$$, you have to count how many dibonacci numbers are in the range $$$[l, r]$$$.

A dibonacci number is an integer whose digits are the sum modulo $$$10$$$ of the two previous digits.

For example, $$$123$$$ is a dibonacci number, because $$$(1 + 2)$$$ mod $$$10 = 3$$$, $$$471$$$ is also a dibonacci number because $$$(4 + 7)$$$ mod $$$10 = 1$$$ and $$$2169$$$ is not a dibonacci number because $$$(1 + 6)$$$ mod $$$10 = 7$$$, which is different from $$$9$$$.

Note that all the positive integers $$$\leq 99$$$ are also dibonacci numbers.

Litusiano was lying in the CAMA while looking at a photo of Emilio when he came up with the following problem:

You are given a permutation $$$p$$$ with some elements missing. Your task is to count how many ways you can fill those missing elements such that the result is still a valid permutation, and the permutation $$$q$$$ obtained by the following process:

For each $$$i$$$ from $$$1$$$ to $$$n$$$ (going from left to right), set $$$q[p[i]] = i$$$.

The resulting permutation $$$q$$$ must be the same as the original permutation $$$p$$$.

You are asked to output the value of the count modulo $$$998244353$$$.

Explanation of permutation:

A permutation is an arrangement of a set of elements in a specific order. For example, for the set $$$\{1, 2, 3\}$$$, the following are some permutations:

- $$$[1, 2, 3]$$$ - $$$[2, 1, 3]$$$ - $$$[3, 1, 2]$$$ - $$$[2, 3, 1]$$$

In this problem, a permutation is defined for a sequence of integers from $$$1$$$ to $$$n$$$. The goal is to fill in missing elements in $$$p$$$ in such a way that it remains a valid permutation and satisfies the given condition for $$$q$$$.

Litusiano was resting on his bed when he thought of the following problem:

You are given two integers, $$$n$$$ and $$$m$$$. Your task is to draw a letter "C" made of the character '#' with height $$$n$$$ and length $$$m$$$. After that, you need to print the word "AMA" at the bottom of the "C".

The "C" should have the following properties:

1. The "C" should have a height of $$$n$$$ rows. 2. The "C" should have a width of $$$m$$$ columns. 3. The top and bottom parts of the "C" should be fully filled with '#'. 4. The left part of the "C" should be a column of '#' characters, except for the top and bottom rows. 5. After printing the "C", print the word "AMA" in the next row.

Are you excited?

Litusiano was listening to La Mafia Del Amor when he came up with the following problem:

You are given $$$n$$$ trees, where the $$$i$$$-th tree has $$$m_i$$$ nodes. You need to answer $$$q$$$ queries.

Each query consists of two integers $$$l$$$ and $$$r$$$. For each query, you are asked to find the minimum diameter of the resulting tree if you optimally merge all the trees in the range $$$[l, r]$$$.

To merge two trees, you add exactly one edge between a node from each tree. Refer to the sample explanation for a better understanding of the merging process.

Note: The diameter of a tree is defined as the longest path between any two nodes in the tree.

Litusiano was reading a book called Rich Dad Poor Dad when he came across the following problem:

You are given an integer $$$n$$$ and an array $$$a$$$ of length $$$n$$$. Your task is to find a permutation $$$p$$$ of length $$$n$$$ (i.e., an arrangement of the numbers from $$$1$$$ to $$$n$$$) that satisfies the following conditions:

1. For every index $$$i$$$ ($$$1 \leq i \leq n$$$): - Let $$$a_i$$$ be the smallest index greater than $$$i$$$ ($$$i \lt a_i \leq n$$$) such that $$$p_i \lt p_{a_i}$$$, or $$$a_i = -1$$$ if no such index exists. 2. The permutation $$$p$$$ must be the lexicographically smallest one that satisfies this property, or it must be determined that no such permutation exists.

Note on lexicographical order:

Lexicographical order (or lexicographically smallest) means that, given two arrays $$$x$$$ and $$$y$$$ of the same length, $$$x$$$ is smaller than $$$y$$$ in this order if at the first position $$$k$$$ where they differ, $$$x_k \lt y_k$$$. For example: - $$$[1, 2, 3]$$$ is smaller than $$$[1, 3, 2]$$$ because at the second position, $$$2 \lt 3$$$. - $$$[2, 1, 3]$$$ is greater than $$$[1, 3, 2]$$$ because at the first position, $$$2 \gt 1$$$.

If no permutation satisfying the given property exists, it should be explicitly stated.

Rigo wants to take a bath, and for that, he needs to fill his bathtub. Rigo has $$$n$$$ buckets of water, each containing $$$p_i$$$ liters, where $$$p$$$ is a permutation of size $$$n$$$. Additionally, his bathtub can hold $$$2n-1$$$ liters if the water is cold and $$$2n+1$$$ liters if it is hot. Although Rigo is a very good mathematician, he is disorganized and has forgotten to label each bucket with its volume, so he asks for your help to assign each bucket its corresponding label in liters.

To do this, you can ask two types of questions:

1. You provide a set of buckets $$$a_0, a_1, \ldots, a_m$$$ $$$(1 \le a_i \le n$$$, and such that there are no $$$i \neq j$$$ with $$$a_i = a_j$$$) and the temperature, cold or hot. In response, Rigo will tell you if you can fit the $$$m$$$ buckets of water at that temperature in the bathtub.
2. You can ask Javi for help. If you give Javi a number $$$r$$$ $$$(1 \le r \le n)$$$, Javi will tell you which $$$i$$$ satisfies $$$p_i = r$$$, but since he is busy playing CS:GO, it will cost you dearly to ask him.

Write a program that returns the permutation $$$p$$$ without running out of coins, making at most $$$2$$$ questions of type $$$2$$$ and $$$100000$$$ questions of type $$$1$$$.

To make a type $$$1$$$ question, the program must have the following format.

• "$$$1$$$ $$$m$$$ $$$c$$$ $$$a_0$$$ $$$a_1$$$ $$$\ldots$$$ $$$a_m$$$" (without quotes). Where $$$m$$$ is the number of buckets you want to include, $$$a_i$$$ are the indices of the buckets you include, and $$$c$$$ is a character that must be 'F' or 'C', where 'F' denotes that the temperature of the water is cold and 'C' that it is hot. There cannot be repeated elements in $$$a$$$.

To make a type $$$2$$$ question, the format must be as follows:

• "$$$2$$$ $$$r$$$" (without quotes). Where $$$r$$$ is the amount of water for which you want to know which bucket has exactly $$$r$$$ liters.

Finally, to provide the answer, the program must print a single line in the following format:

• "! $$$p_0$$$ $$$p_1$$$ $$$\ldots$$$ $$$p_n$$$" (without quotes).

If your program asks more than $$$2$$$ questions of type $$$2$$$ or $$$10^5$$$ questions of type $$$1$$$ for a test case, it must terminate immediately to receive the verdict Wrong Answer. Otherwise, you could receive an arbitrary verdict because your solution will attempt to continue reading from a closed stream.

Additionally, the sum of $$$m$$$ over all questions of type $$$1$$$ over all tests must not exceed $$$10^7$$$.

After printing a question or the answer, do not forget to write the end-of-line character and flush the output buffer. Otherwise, you might get the verdict Time limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++.
• System.out.flush() in Java.
• stdout.flush() in Python.
• Check the documentation for other languages.