You are given two integers $$$n$$$ and $$$k$$$.

There's an $$$n\times n$$$ grid. At each step, you can move one cell up, down, left, or right, but you cannot move out of bounds. At first, all cells in the grid are white. You need to color some cells black, such that no matter how you move from the top-left corner to the bottom-right corner, you pass through at least $$$k$$$ number of black cells.

Find the minimum number of black cells required to be colored to satisfy the condition above.

You're given an array $$$a$$$ of size $$$n$$$ and an array $$$b$$$ of size $$$m$$$.

Find the minimum $$$k$$$ such that $$$a$$$ is a subsequence$$$^\dagger$$$ of $$$dup(b, k)$$$. If there's no such $$$k$$$, output $$$-1$$$ instead.

Here $$$dup(b,k)=[b_1,b_2,\ldots,b_m,b_1,b_2,\ldots,b_m,\ldots]$$$($$$k$$$ times). More formally, $$$dup(b,k)$$$ is an array $$$x$$$ of length $$$m \cdot k$$$, where $$$x_i = b _{(i-1)\ mod\ m\ +\ 1}$$$ for all $$$1 \le i \le m \cdot k$$$.

$$$^\dagger$$$A subsequence of a sequence is a sequence that is formed by selecting zero or more elements from the original sequence while maintaining the relative order of the selected elements.

You're given an $$$n \times n$$$ square matrix. At first, all elements in this matrix are zero.

You need to change $$$n$$$ elements in the matrix so that $$$1,2, \ldots ,n$$$ appears exactly once.

A square matrix of size $$$n \times n$$$ is considered perfect if its number of good square submatrices reaches maximum. A square submatrix of size $$$m \times m (m \le n)$$$ is considered good if it contains the integer $$$m$$$.

Count the number of possible perfect square matrices. Since the answer may be large, output the answer modulo $$$998\,244\,353$$$.

You are given a tree with $$$n$$$ nodes. At first, the value of the $$$i$$$-th node is $$$a_i$$$.

The two nodes can be merged only if the following two conditions hold:

1. The values of the two nodes are equal;
2. They are connected by an edge.

In the $$$i$$$-th merging, a new node with number $$$(n+i)$$$ is created. Assume we'll merge node $$$x$$$ and $$$y$$$, we set the value of node $$$(n+i)$$$ to the sum of the value of node $$$x$$$ and $$$y$$$, and we add edges of node $$$(n+i)$$$ and all the nodes connected to node $$$x$$$ and $$$y$$$, except $$$x$$$ and $$$y$$$ themselves. After that, node $$$x$$$ and $$$y$$$ will be removed.

Find if it's possible to merge all nodes into one node.

You have been given a bracket sequence $$$s_1 s_2 \dots s_n$$$ of length $$$n$$$. The score of the sequence $$$s$$$ is the number of pairs $$$(l,r)$$$ such that $$$1 \leq l \leq r \leq n$$$ and $$$s_l s_{l+1} \dots s_r$$$ forms a regular bracket sequence$$$^\dagger$$$.

There are $$$q$$$ operations which will be performed on $$$s$$$. The $$$i$$$-th operation is described as follows:

• Swap the $$$p_i$$$-th character with the $$$(p_i+1)$$$-th character in $$$s$$$. The effect of this operation is permanent, meaning that the sequence $$$s$$$ is permanently modified after this operation.

For each $$$i$$$ such that $$$1 \leq i \leq q$$$, calculate the score of $$$s$$$ after the $$$i$$$-th operation is performed.

$$$^\dagger$$$A regular bracket sequence is a bracket sequence where if we add + and 1 into the sequence, it is possible for us to get a correct mathematical expression. For example, (), ((())), and ()(()) are all regular bracket sequences, while )(, ((), and ())(()() are not.

You're given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$,and an array of $$$q$$$ integers $$$x_1, x_2, \ldots, x_q$$$. It is guaranteed that all integers $$$a_1, a_2, \ldots, a_n, x_1, x_2, \ldots, x_q$$$ are distinct.

You need to answer $$$q$$$ queries. For the $$$i$$$-th query, find the height$$$^\dagger$$$ of the BST(binary search tree) constructed by inserting $$$n + 1$$$ elements in the order of $$$x_i, a_1, a_2, \ldots, a_n$$$.

Formally, for the $$$i$$$-th query, we set the BST $$$T$$$ empty initially. Then, we run the function $$$\texttt{insert}(T, x_i), \texttt{insert}(T, a_1), \texttt{insert}(T, a_2), \ldots , \texttt{insert}(T, a_n)$$$ in order.

function insert(T, x)
    if T is null:
        newNode = Node(x) // Create a new node with value x
        T = newNode       // Set newNode as the root of the tree
    else if x < T.value:
        T.left = insert(T.left, x)   // Recursively insert x into the left subtree
    else if x > T.value:
        T.right = insert(T.right, x) // Recursively insert x into the right subtree
    return T                         // Return the root of the modified tree

$$$^\dagger$$$The height of a tree refers to the length of the longest path from the root node to any leaf node in the tree. It represents the number of edges on the longest downward path between the root node and a leaf.