You are given an array $$$b_1, b_2, \ldots, b_n$$$.

An anonymous informant has told you that the array $$$b$$$ was obtained as follows: initially, there existed an array $$$a_1, a_2, \ldots, a_n$$$, after which the following two-component operation was performed $$$k$$$ times:

1. A fixed point$$$^{\dagger}$$$ $$$x$$$ of the array $$$a$$$ was chosen.
2. Then, the array $$$a$$$ was cyclically shifted to the left$$$^{\ddagger}$$$ exactly $$$x$$$ times.

As a result of $$$k$$$ such operations, the array $$$b_1, b_2, \ldots, b_n$$$ was obtained. You want to check if the words of the anonymous informant can be true or if they are guaranteed to be false.

$$$^{\dagger}$$$A number $$$x$$$ is called a fixed point of the array $$$a_1, a_2, \ldots, a_n$$$ if $$$1 \leq x \leq n$$$ and $$$a_x = x$$$.

$$$^{\ddagger}$$$A cyclic left shift of the array $$$a_1, a_2, \ldots, a_n$$$ is the array $$$a_2, \ldots, a_n, a_1$$$.

You are given an array $$$a$$$ consisting of $$$n$$$ integers, as well as an array $$$b$$$ consisting of $$$m$$$ integers.

Let $$$\text{LIS}(c)$$$ denote the length of the longest increasing subsequence of array $$$c$$$. For example, $$$\text{LIS}([2, \underline{1}, 1, \underline{3}])$$$ = $$$2$$$, $$$\text{LIS}([\underline{1}, \underline{7}, \underline{9}])$$$ = $$$3$$$, $$$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])$$$ = $$$3$$$.

You need to insert the numbers $$$b_1, b_2, \ldots, b_m$$$ into the array $$$a$$$, at any positions, in any order. Let the resulting array be $$$c_1, c_2, \ldots, c_{n+m}$$$. You need to choose the positions for insertion in order to minimize $$$\text{LIS}(c)$$$.

Formally, you need to find an array $$$c_1, c_2, \ldots, c_{n+m}$$$ that simultaneously satisfies the following conditions:

• The array $$$a_1, a_2, \ldots, a_n$$$ is a subsequence of the array $$$c_1, c_2, \ldots, c_{n+m}$$$.
• The array $$$c_1, c_2, \ldots, c_{n+m}$$$ consists of the numbers $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_m$$$, possibly rearranged.
• The value of $$$\text{LIS}(c)$$$ is the minimum possible among all suitable arrays $$$c$$$.

Let's define the anti-beauty of a multiset $$$\{b_1, b_2, \ldots, b_{len}\}$$$ as the number of occurrences of the number $$$len$$$ in the multiset.

You are given $$$m$$$ multisets, where the $$$i$$$-th multiset contains $$$n_i$$$ distinct elements, specifically: $$$c_{i, 1}$$$ copies of the number $$$a_{i,1}$$$, $$$c_{i, 2}$$$ copies of the number $$$a_{i,2}, \ldots, c_{i, n_i}$$$ copies of the number $$$a_{i, n_i}$$$. It is guaranteed that $$$a_{i, 1} \lt a_{i, 2} \lt \ldots \lt a_{i, n_i}$$$. You are also given numbers $$$l_1, l_2, \ldots, l_m$$$ and $$$r_1, r_2, \ldots, r_m$$$ such that $$$1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i}$$$.

Let's create a multiset $$$X$$$, initially empty. Then, for each $$$i$$$ from $$$1$$$ to $$$m$$$, you must perform the following action exactly once:

1. Choose some $$$v_i$$$ such that $$$l_i \le v_i \le r_i$$$
2. Choose any $$$v_i$$$ numbers from the $$$i$$$-th multiset and add them to the multiset $$$X$$$.

You need to choose $$$v_1, \ldots, v_m$$$ and the added numbers in such a way that the resulting multiset $$$X$$$ has the minimum possible anti-beauty.

You have $$$n$$$ colored cubes, the $$$i$$$-th cube has color $$$a_i$$$.

You need to distribute all the cubes on shelves. There are a total of $$$m$$$ shelves, the $$$i$$$-th shelf can hold $$$s_i$$$ cubes. Also, $$$s_1 + s_2 + \ldots + s_m = n$$$.

Suppose on a shelf of size $$$k$$$ there are cubes of colors $$$c_1, c_2, \ldots, c_k$$$, in this order. Then we define the colorfulness of the shelf as the minimum distance between two different cubes of the same color on the shelf. If all the cubes on the shelf have different colors, then the colorfulness is considered to be equal to the size of the shelf, that is, the number $$$k$$$.

More formally, the colorfulness of $$$c_1, c_2, \ldots, c_k$$$ is defined as follows:

• If all the colors $$$c_1, c_2, \ldots, c_k$$$ are different, the colorfulness is considered to be $$$k$$$.
• Otherwise, the colorfulness is considered to be the smallest integer $$$x \geq 1$$$ such that there exists an index $$$i$$$ $$$(1 \le i \le k - x)$$$ such that $$$c_i = c_{i+x}$$$.

For each shelf, you are given the minimum required colorfulness, that is, you are given numbers $$$d_1, d_2, \ldots, d_m$$$, which mean that shelf $$$i$$$ must have a colorfulness $$$\geq d_i$$$ for all $$$i$$$.

Distribute the available cubes among the shelves to ensure the required colorfulness, or report that it is impossible.

You are given an undirected connected graph in which any two distinct simple cycles do not have common vertices. Since the graph can be very large, it is given to you in a compressed form: for each edge, you are also given a number $$$d$$$, which indicates that there are $$$d$$$ additional vertices on this edge.

You need to assign a weight to each vertex and each edge of the graph — an integer from $$$1$$$ to $$$3$$$.

An edge of the graph is called good if the bitwise XOR of the weights of its adjacent vertices is not equal to $$$0$$$ and not equal to the weight of that edge.

Similarly, a vertex of the graph is called good if the bitwise XOR of the weights of its adjacent edges is not equal to $$$0$$$ and not equal to the weight of that vertex.

You need to determine how many ways there are to assign weights to the vertices and edges of the graph so that all vertices and edges are good. Since the answer can be quite large, you need to calculate the remainder of the answer divided by $$$998\,244\,353$$$.