Aris is playing the classic game, Angry Birds!

Because Aris has been playing for too long, Yuuka confiscated Aris's game console and demanded that Aris complete today's math homework before getting it back.

However, Sensei did not assign any math homework to Aris today, so Yuuka had to come up with a problem for Aris to solve.

Consider the game field of Angry Birds as a three-dimensional Euclidean space, and the bird as a sphere with radius $$$ R_3 $$$. Establish a spatial Cartesian coordinate system $$$ O-xyz $$$, such that the trajectory of the bird's center lies in the horizontal plane $$$ z=0 $$$.

It is known that the trajectory of the bird's center is a closed polyline, consisting of $$$ n $$$ segments connected end to end. The connection points are $$$ n $$$ points: $$$ (x_1, y_1, 0), (x_2, y_2, 0), \cdots, (x_n, y_n, 0) $$$. The $$$ i $$$-th segment has endpoints $$$ (x_i, y_i, 0) $$$ and $$$ (x_{i \bmod n + 1}, y_{i \bmod n + 1}, 0) $$$. However, due to sensor errors, the actual $$$ n $$$ points may deviate from $$$ (x_i, y_i, 0) $$$ by a distance not exceeding $$$ R_2 $$$ (the sensor deviation $$$ R_2 $$$ is the same for all points). That is, the actual $$$ i $$$-th point $$$ (x'_i, y'_i, 0) $$$ can be anywhere within the circle (which is still contained in the plane $$$ z=0 $$$) centered at $$$ (x_i, y_i, 0) $$$ with radius $$$ R_2 $$$.

Let $$$ S $$$ be the set of all points that the entire bird may pass through, i.e., points in 3D space whose distance to the bird's center trajectory is at most $$$ R_3 $$$. Yuuka requires Aris to compute the volume of the convex hull of $$$ S $$$.

Convex hull: The convex hull of a point set $$$ S $$$ is defined as the smallest set $$$ T $$$ such that for any two points in $$$ S $$$, all points on the line segment between them are contained in $$$ T $$$.

Mr. Noya has a pet hamster that loves to gnaw on wood.

One day, Mr. Noya brought home a rectangular wooden block with dimensions $$$L \times W \times H$$$, meaning it has a length of $$$L$$$ units, a width of $$$W$$$ units, and a height of $$$H$$$ units, divided into $$$L \times W \times H$$$ unit cubes. Using one vertex of the block as the origin, the length direction as the $$$x$$$-axis, the width direction as the $$$y$$$-axis, and the height direction as the $$$z$$$-axis, a spatial coordinate system $$$O-xyz$$$ is established. The unit cube with $$$x$$$-coordinate in $$$[i-1, i)$$$, $$$y$$$-coordinate in $$$[j-1, j)$$$, and $$$z$$$-coordinate in $$$[k-1, k)$$$ is denoted as $$$(i, j, k)$$$.

Note: The block does not necessarily have length greater than width (i.e., it is not required that $$$W \leq L$$$); the terms are just used to fix the directions.

Mr. Noya does not want the wooden block to be completely gnawed away by his hamster, so he decides to reinforce it. Reinforcing the unit cube at $$$(i,j,k)$$$ has a cost $$$V(i,j,k)$$$. Additionally, there are three matrices $$$A,B,C$$$ representing constraints from the three orthogonal views (front view, side view, and top view):

• For matrix $$$A = \{a_{ij}\}_{H \times L}$$$, if $$$a_{ij} = 0$$$, then for all $$$1 \leq p \leq W$$$, the cube at $$$(j, p, i)$$$ must not be reinforced. If $$$a_{ij} = 1$$$, at least one of these cubes must be reinforced.
• For matrix $$$B = \{b_{ij}\}_{H \times W}$$$, if $$$b_{ij} = 0$$$, then for all $$$1 \leq q \leq L$$$, the cube at $$$(q, j, i)$$$ must not be reinforced. If $$$b_{ij} = 1$$$, at least one of these cubes must be reinforced.
• For matrix $$$C = \{c_{ij}\}_{W \times L}$$$, if $$$c_{ij} = 0$$$, then for all $$$1 \leq r \leq H$$$, the cube at $$$(j, i, r)$$$ must not be reinforced. If $$$c_{ij} = 1$$$, any number (including zero) of these cubes may be reinforced.

Note: Mr. Noya can reinforce each unit cube at most once.

Note: For matrix $$$C$$$, a non-zero value does not require reinforcing at least one unit cube.

Under the above conditions, Mr. Noya wants to minimize the total cost of reinforcing the wooden block. Can you help him?

Note: You do not need to consider the issue of unit cubes being suspended in air.

There are three students training hard for ICPC. They are practicing on a problemset consisting of exactly $$$S$$$ problems. Each problem belongs to exactly one of the following seven categories, describing which subset of students can solve it:

• $$$F_1$$$: only student $$$1$$$ can solve;
• $$$F_2$$$: only student $$$2$$$ can solve;
• $$$F_3$$$: students $$$1$$$ and $$$2$$$ (but not $$$3$$$) can solve;
• $$$F_4$$$: only student $$$3$$$ can solve;
• $$$F_5$$$: students $$$1$$$ and $$$3$$$ (but not $$$2$$$) can solve;
• $$$F_6$$$: students $$$2$$$ and $$$3$$$ (but not $$$1$$$) can solve;
• $$$F_7$$$: students $$$1$$$, $$$2$$$ and $$$3$$$ can all solve.

It is guaranteed that $$$$$$ F_1 + F_2 + F_3 + F_4 + F_5 + F_6 + F_7 = S. $$$$$$

You are going to assign each problem to exactly one student who can solve it. Your goal is to make the training as balanced as possible: maximize the minimum number of problems solved by any single student. Output this maximum possible value.

You have $$$N$$$ Arcane Behemoths, each with an attack value $$$A_i$$$.

You may choose any non-empty subsequence of Behemoths and sell them one by one. Whenever you sell a Behemoth, each remaining unsold Behemoth in the subsequence increases its attack value by the attack value of the Behemoth you just sold.

The value of a subsequence is the maximum attack value the last remaining Behemoth can achieve, if the other Behemoths in the subsequence are sold in an optimal order.

Your task is to compute the sum of values over all non-empty subsequences of the sequence. Print the result modulo $$$998244353$$$.

An integer sequence $$$a_1,a_2,\cdots,a_n$$$ is called a zero sequence if and only if it satisfies the following conditions:

• For $$$i=1,2,\cdots,n-1$$$, $$$a_i \neq a_{i+1}$$$.
• The binary XOR sum of $$$a_1,a_2,\cdots,a_n$$$ is $$$0$$$, i.e., $$$$$$ \bigoplus_{i=1}^{n}a_i=0 $$$$$$

Given $$$n$$$ and $$$m$$$, find the number of zero sequences of length $$$n$$$ where each element is chosen from the set $$$\{0,1,2,\cdots,2^m-1\}$$$.

Give two permutations $$$p$$$ and $$$q$$$ of length $$$n$$$. It is guaranteed that $$$n$$$ is an odd number. You must perform exactly one of the following operations for each position $$$i \in [1,n]$$$:

1. Perform no operation at no cost.
2. Spend a cost of $$$x_i$$$ to either modify $$$p_i$$$ to $$$p_i^2$$$ or modify $$$q_i$$$ to $$$q_i^2$$$.
3. Spend a cost of $$$y_i$$$ to modify both $$$p_i$$$ to $$$p_i^2$$$ and $$$q_i$$$ to $$$q_i^2$$$.

Please find the minimum cost required to make the median of array $$$p$$$ equal to $$$A$$$ and the median of array $$$q$$$ equal to $$$B$$$. If it's impossible, output $$$-1$$$.

Give two permutations $$$p$$$ and $$$q$$$ of length $$$n$$$. It is guaranteed that $$$n$$$ is an odd number. You must perform exactly one of the following operations for each position $$$i \in [1,n]$$$:

1. Perform no operation at no cost.
2. Spend a cost of $$$x$$$ to either modify $$$p_i$$$ to $$$p_i^2$$$ or modify $$$q_i$$$ to $$$q_i^2$$$.
3. Spend a cost of $$$y$$$ to modify both $$$p_i$$$ to $$$p_i^2$$$ and $$$q_i$$$ to $$$q_i^2$$$.

There are a total of $$$m$$$ groups of queries in this problem. For each query, values of $$$x$$$ , $$$y$$$ , $$$A$$$ and $$$B$$$ are given.Please find the minimum cost required to make the median of array $$$p$$$ equal to $$$A$$$ and the median of array $$$q$$$ equal to $$$B$$$. If it's impossible, output $$$-1$$$.

Froggy has an unrooted tree $$$T$$$ with $$$n$$$ vertices, where each vertex has an initial weight. Initially, the weight of vertex $$$i$$$ is $$$i$$$.

Froggy can perform at most 1 operation sequentially as follows:

• Select several distinct vertices $$$x_1, x_2, \cdots, x_k$$$, such that for $$$i = 1, 2, \cdots, k-1$$$, there exists an edge in tree $$$T$$$ connecting vertex $$$x_i$$$ and vertex $$$x_{i+1}$$$.
• From the set $$${x_1, x_2, \cdots, x_k}$$$, choose an even number of vertices $$$u_1, u_2, \cdots, u_{2l}$$$ (vertices can be chosen repeatedly). For $$$i = 1, 2, \cdots, l$$$, sequentially swap the weights of vertex $$$u_{2i-1}$$$ and vertex $$$u_{2i}$$$.

Let $$$a_i$$$ denote the weight of vertex $$$i$$$ after all operations. How many distinct sequences $$$a_1, a_2, \cdots, a_n$$$ can Froggy obtain? Output the answer modulo $$$998244353$$$.

This is an interactive problem.

Given a directed acyclic graph (DAG) with $$$n$$$ vertices and $$$m$$$ edges, each edge has an associated weight.

There may be multiple paths between any pair of vertices $$$s$$$ and $$$t$$$. We define the weight of a path as the product of the weights of all edges along that path. Let $$$f(s,t,c)$$$ denote the sum of the path weights of all distinct paths from $$$s$$$ to $$$t$$$ after multiplying the weight of every edge in the graph by $$$c$$$. Since the result can be extremely large, $$$f(s,t,c)$$$ is taken modulo $$$998244353$$$.

Xiao M will inform you of the structure of the DAG in advance (excluding the edge weights).

You may provide parameters $$$s$$$, $$$t$$$, and $$$c$$$; the interactor will return the value of $$$f(s,t,c)$$$. You are allowed to make at most $$$999$$$ such queries to obtain certain information about the graph. After several query cycles, the interactor will provide a parameter $$$k$$$, and you need to determine the value of $$$f(1,n,k)$$$.

For each query, you need to output in the format $$$\texttt{? s t c}$$$ $$$(1\leq s,t\leq n,0\leq c \lt 998244353)$$$ where $$$s,t,c$$$ are all integers, and the interactor will return the answer of $$$f(s,t,c)$$$.

When you are confident that the information you have is sufficient to answer the query, output $$$\texttt{!}$$$, and the interactor will return a integer parameter $$$k$$$ $$$(0\leq k \lt 998244353)$$$, which means you are asked for the weight of $$$f(1,n,k)$$$.

You need to output the result of $$$f(1,n,k)$$$.

After printing a query or the answer, do not forget to output the end of the line and flush the output. Otherwise, you will get the verdict Idleness Limit Exceeded. To do this, use:

$$$\texttt{fflush(stdout)}$$$ or $$$\texttt{cout.flush()}$$$ in C++; $$$\texttt{System.out.flush()}$$$ in Java; $$$\texttt{flush(output)}$$$ in Pascal; $$$\texttt{stdout.flush()}$$$ in Python; see the documentation for other languages.

You are given a remembered collection of $$$\textit{diameter endpoint pairs}$$$ that Little Grey wrote down when he owned a tree with $$$N$$$ nodes. Now he forgot the tree itself. Your task is to reconstruct $$$\textbf{any}$$$ tree on $$$N$$$ labeled nodes whose set of unordered pairs of nodes at distance equal to the tree diameter is exactly the given collection — or report that his memory is inconsistent (i.e. no such tree exists).

A $$$\textit{diameter}$$$ of a tree is the longest simple path in the tree; its length is the maximum distance between any two vertices. A pair $$$(u,v)$$$ is a $$$\textit{diameter endpoint pair}$$$ if the distance between $$$u$$$ and $$$v$$$ equals the length of tree diameter. The given collection contains unordered pairs and may list them in any order.

Kikyou has carefully cultivated a tree. Now that the tree has grown lush with branches and leaves, Kikyou decides to prune it.

The tree currently has $$$n$$$ vertices. Kikyou plans to remove some vertices and their adjacent edges such that the remaining part is still connected. It is easy to see that the remaining part is still a tree.

As a heavy cat, Kikyou wants the remaining tree to be wholehearted, meaning it has only one heart. Here, the heart of a tree is defined as a vertex such that when it is removed, the maximum size among the remaining connected components is minimized. If multiple vertices satisfy this condition, they are all considered hearts.

Kikyou wants to know how many such remaining non-empty trees there are where the heart is unique. Output the answer modulo $$$998244353$$$. Two remaining trees are considered different if and only if their vertex sets are different.

Long ago, in the land of Bitworld, there was a magic mirror. Whenever you looked into it, the index $$$i$$$ of an array element would be reflected as $$$i \oplus k$$$ for some magic key $$$k$$$. The wizard who owned this mirror loved to play with sequences: sometimes he mirrored parts of the sequence using XOR, and sometimes he asked for weighted sums of intervals.

Now the wizard gives you $$$T$$$ sequences and a list of operations for each sequence. Your task is to process them and report the results of his queries.

You are given an initial sequence $$$A_0, A_1, \dots, A_{N-1}$$$ of length $$$N$$$. The value $$$N$$$ is always a power of two and satisfies $$$N \le 2^{18}$$$.

There are two types of operations:

• Operation type 1: given integers $$$(l,r,k)$$$, for every $$$i \in [l,r)$$$ set $$$$$$ B_i = A_{i \oplus k}, $$$$$$ then assign $$$A_i = B_i$$$ for all $$$i \in [l,r)$$$.
• Operation type 2: given integers $$$(l,r)$$$, output $$$$$$ \sum_{i=l}^{r-1} A_i. $$$$$$