You are given a permutation $$$p$$$ of integers $$$1$$$ to $$$n$$$. You need to partition $$$p$$$ into two disjoint increasing subsequences such that the difference between the sizes of these subsequences is the maximum possible. Note that each element must belong to exactly one of the subsequences. The empty subsequence is also allowed.

You are given two integers $$$n$$$ and $$$k$$$. Determine whether there exists an array $$$a_0$$$, $$$a_1$$$, $$$\ldots$$$, $$$a_{n-1}$$$ with the properties:

• it contains all integers from the interval $$$[0,n-1]$$$ exactly once,
• for each $$$i \in [0,n-1]$$$, we have $$$(a_i + a_{(i + 2) \pmod n}) \pmod k = 0$$$.

You are given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered by integers from $$$1$$$ to $$$n$$$. Each vertex has a value written in it; the value in the vertex $$$v$$$ is equal to $$$c_v$$$.

A walk between two vertices $$$v_1$$$ and $$$v_k$$$ is defined as a sequence of vertices $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ such that the vertices $$$v_i$$$ and $$$v_{i+1}$$$ are connected by an edge for all $$$1 \leq i \leq k-1$$$. Note that the same vertex and even the same edge can occur multiple times in a walk.

We define the median of $$$k$$$ numbers to be the $$$\left\lfloor\frac{k}{2}+1 \right\rfloor$$$-th largest number (the $$$1$$$-st largest number is the smallest). The brackets $$$\lfloor \rfloor$$$ denote rounding the number to the highest integer not exceeding it. For this task, we define the value of a walk to be the median value of the values of all vertices in the walk. Note that if the walk has length $$$k$$$, you should consider $$$k$$$ numbers (that is, you should consider each vertex as many times as it is visited).

Find the smallest possible value of a walk between vertices $$$1$$$ and $$$n$$$!

You are given a string $$$s$$$ of length $$$n$$$ that consists of lowercase English letters. We call a sequence of letters a word if it consists of at least one vowel and at least one consonant. What is the maximum number of words the given string can be partitioned into?

In this problem, we consider the vowels to be the letters a, i, o, u, e, y, and all the other letters are consonants.

You are an ice cream man. You serve portions of ice cream filling a cone up to some level, and top it with two equally-sized flavored gelato balls. You are also generous, and want to put the largest balls you can. Both balls have to touch the main portion of the ice cream. The balls can touch, but not intersect. The balls can also touch, but not intersect the cone. What is the maximum possible radius of the ice cream balls?

Also, you live in 2D, so the cone is actually an isosceles triangle, and the balls are not spheres, but circles.

Given

• the height of the cone $$$h$$$,
• the level of the main ice cream portion inside the cone $$$\ell$$$,
• the width of the cone top $$$w$$$,

You are given a strip of paper that consists of $$$n$$$ consecutive square cells. The cells are numbered $$$1$$$ to $$$n$$$ from left to right. Each cell has an integer written in it, which is either $$$0$$$, $$$1$$$, or $$$2$$$. Denote the integer in the $$$i$$$-th cell by $$$a_i$$$. You can color black any number of the left or right borders of these cells (there are $$$n+1$$$ such borders in total). Is it possible to color the borders in such a way that for each cell $$$i$$$, the number of its borders that is colored is equal to $$$a_i$$$?

For example, if you are given the numbers $$$1~2~1~0~1~2$$$, then it is possible to color the borders as follows:

You are given $$$n$$$ strings, and you need to answer $$$q$$$ queries. Each query is composed of two strings $$$l_i$$$ and $$$r_i$$$. For such a query, you need to count the number of the given strings such that either it has $$$l_i$$$ as a prefix, $$$r_i$$$ as a suffix, or both (thus, a string that has $$$l_i$$$ for a prefix and $$$r_i$$$ for a suffix should be counted once).

You are given a tree with $$$n$$$ vertices. Every vertex $$$v$$$ has two values $$$a_v$$$ and $$$b_v$$$. You have to process $$$q$$$ queries of types:

1. Given $$$v$$$ and $$$x$$$, assign $$$a_v = x$$$;
2. Given $$$v$$$, print $$$a_v$$$;
3. Given $$$v$$$, implement the following procedure efficiently:

   First, create an array $$$\text{used}[1\ldots n]$$$ filled with false initially. Then run the function $$$\text{DFS}(v)$$$:

   
       DFS(v):
       {
           used[v] = true;
           for u from 1 to n do
           {
               if (u and v are connected by an edge)
                  and (used[u] == false)
                  and (a[v] + b[u] == a[u] + b[v]) then
               {
                   DFS(u);
               }
           }
           a[v] = b[v];
       }
   

You are given a multiset of integers, which is initially empty. Then you need to process $$$q$$$ queries. With each query, you either add or remove a single integer in the multiset.

After each query you need to calculate the maximum possible mex of the multiset you can obtain, if you can apply the following operations. With a single operation, you can take an element $$$x$$$ that appears at least twice in the multiset, remove one of them and add either $$$x-1$$$ or $$$x+1$$$. These operations do not affect the multiset for the next query.

Mex stands for "minimum excluded": the mex of a multiset of numbers is equal to the smallest non-negative integer which is not present in the multiset. For example, $$$\text{mex}(\{0,1,1,2,4,4\})=3$$$. However, in this problem you can convert this multiset to $$$\{0,1,2,3,4,5\}$$$, in which case mex becomes $$$6$$$.

You are given two arrays of integers $$$a$$$ and $$$b$$$. The length of $$$a$$$ is $$$n$$$ and the length of $$$b$$$ is $$$m$$$. Your task is to find any matrix $$$C$$$ of size $$$n \times m$$$, which satisfies all of the following properties:

• all integers in the interval $$$[0,n\cdot m-1]$$$ should be in $$$C$$$ exactly once,
• the mex of the $$$i$$$-th row should be equal to $$$a_i$$$,
• the mex of the $$$j$$$-th column should be equal to $$$b_j$$$.

Mex stands for "minimum excluded": the mex of a set of numbers is equal to the smallest non-negative integer which is not present in the set. For example, $$$\text{mex}(\{0,1,2,4\})=3$$$.

You are given a sequence of $$$n$$$ bits $$$a_1$$$, $$$\ldots$$$, $$$a_n$$$ (each bit can be either $$$0$$$ or $$$1$$$). Initially all bits are set to $$$0$$$. You are also given $$$m$$$ pairs of indices $$$(i,j)$$$, which are the possible operations you can apply to the sequence. If you apply an operation $$$(i,j)$$$, $$$a_i$$$ changes to $$$1-a_i$$$ and $$$a_j$$$ to $$$1-a_j$$$.

You are also given a target sequence of $$$n$$$ bits $$$b_1$$$, $$$\ldots$$$, $$$b_n$$$. Determine if it is possible to obtain $$$b$$$ from $$$a$$$ by applying the available operations (you can also not change the array at all). Each operation can be applied zero or multiple times, and operations may be appplied in any order.

You are in charge of a storage room, which is formed by two infinite diagonal walls joining in a single point at the bottom. There are $$$n$$$ equally sized square boxes in the storage. The boxes are naturally pulled by gravity. For example, the placement of the boxes could be as follows:

Then the bottom box is removed from the storage. The other boxes start to fall into the now empty space until a stable arrangement is reached again. The boxes can fall in different ways, depending on whether the left or the right upper box fills the empty slot. For example, in the previous figure, there are 3 different options:

Find the total number of different possible falling scenarios modulo $$$10^9+7$$$.

You are given an infinite table $$$A$$$. The rows and columns are indexed by integers $$$0$$$, $$$1$$$, $$$2$$$, and so on. The number in the $$$i$$$-th row and $$$j$$$-th column is equal to $$$A_{i,j} = 2^i 3^j$$$.

$$$$$$ \begin{array}{c||c|c|c|c|c} & 0 & 1 & 2 & 3 & \ldots \\ \hline\hline 0 & 1 & 3 & 9 & 27 & \ldots \\ \hline 1 & 2 & 6 & 18 & 54 & \ldots \\ \hline 2 & 4 & 12 & 36 & 108 & \ldots \\ \hline 3 & 8 & 24 & 72 & 216 & \ldots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} $$$$$$

You need to process $$$q$$$ queries of the form $$$(i_1,i_2,j_1,j_2)$$$, where $$$i_1 \leq i_2$$$ and $$$j_1 \leq j_2$$$. For each query, you need to calculate the value $$$$$$\sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A_{i,j}$$$$$$ modulo $$$10^9+7$$$.