An $$$n\times m$$$ sudoku puzzle is a grid consisting of $$$m\times n$$$ regions, and each region contains $$$n\times m$$$ cells. Hence an $$$n\times m$$$ sudoku puzzle contains $$$nm\times nm$$$ cells. Every integer from $$$1$$$ to $$$nm$$$ occurs exactly once in each row, each column, and each region of an $$$n\times m$$$ sudoku puzzle.

Listing the integers in a row or a column starting from some direction as a sequence of length $$$nm$$$, $$$X$$$ is the first integer of the sequence, and X-sum is the sum of the first $$$X$$$ integers of the sequence.

The above figure is a $$$4\times 2$$$ sudoku puzzle with X-sums. The $$$7$$$-th row listed from right to left is $$$[3,4,1,2,7,8,5,6]$$$ and the first integer $$$X$$$ is $$$3$$$, so the X-sum of the $$$7$$$-th row from the direction right is $$$8=3+4+1$$$.

Given two positive integers $$$n$$$ and $$$m$$$, a direction $$$d$$$, and an index $$$x$$$, you need to find the X-sum of the $$$x$$$-th row or $$$x$$$-th column from the direction $$$d$$$ in the lexicographically smallest $$$2^n\times 2^m$$$ sudoku.

Denoting $$$a_{i,j}$$$ as the $$$i$$$-th row and the $$$j$$$-th column of a sudoku puzzle $$$a$$$, a sudoku puzzle $$$a$$$ is lexicographically smaller than a sudoku puzzle $$$b$$$ of the same size if there exists $$$i$$$ and $$$j$$$ satisfying that $$$a_{i,j} \lt b_{i,j}$$$, that $$$a_{x,y}=b_{x,y}$$$ for all $$$x \lt i$$$, and that $$$a_{x,y}=b_{x,y}$$$ for all $$$x=i$$$ and $$$y \lt j$$$. You can find that the above is the lexicographically smallest $$$4\times 2$$$ sudoku puzzle.

Patrick's Parabox is a Sokoban-like game. A Sokoban puzzle is a grid, and each cell is a wall or a floor. There are several boxes and a player in some distinct floor cells, and they can not move to the wall cells or coincide. You can control the player to move in one of four directions, left, right, up, and down. When the player touches a box, it can push the box. The target is to move all boxes to some target cells.

Please read the following rules carefully. They may be different from the usual rules.

In this problem, there is only one box, and the box is the grid itself. That means if the player moves out of the grid, they may be "teleported" to a cell adjacent to the box; if the player moves to the box, they may be "teleported" to a cell on the boundary of the grid. Besides, there is also a target cell for the player. The player needs to move to the target cell at the end too.

Given a puzzle, you need to find the minimum number of times to push the box, such that the box and the player can arrive to their respective target cells.

The following are the detailed and formal rules.

Consider an $$$n\times m$$$ grid. Denote $$$(i,j)$$$ as the cell in $$$i$$$-th row and $$$j$$$-th column. The rows are numbered $$$1, 2, \ldots, n$$$ from top to bottom, and the columns are numbered $$$1, 2, \ldots, m$$$ from left to right.

Denote W, S, A, and D as the control commands, which mean to move up, down, left, and right respectively.

Define that $$$v_\text{W}=(-1,0)$$$, $$$v_\text{S}=(1,0)$$$, $$$v_\text{A}=(0,-1)$$$, $$$v_\text{D}=(0,1)$$$.

Define that $$$w_\text{W}=(n,\left\lceil\dfrac m2\right\rceil)$$$, $$$w_\text{S}=(1,\left\lceil\dfrac m2\right\rceil)$$$, $$$w_\text{A}=(\left\lceil \dfrac n2\right\rceil,m)$$$, $$$w_\text{D}=(\left\lceil \dfrac n2\right\rceil,1)$$$.

In each operation, you can choose one of the control commands $$$c$$$, one of W, S, A, and D. Denote $$$p$$$ as the cell which contains the player and $$$b$$$ as the cell which contains the box before the operation:

• If $$$p+v_c=b$$$ and $$$b+v_c$$$ is a floor cell, the player moves to $$$p+v_c$$$ and the box moves to $$$b+v_c$$$. Only this case counts towards the answer, and so has to happen the minimum possible number of times.
• If $$$p+v_c$$$ is a wall cell, nothing happens.
• If $$$p+v_c$$$ is a floor cell and $$$p+v_c\ne b$$$, the player moves to $$$p+v_c$$$.
• If $$$p+v_c=b$$$ and $$$b+v_c$$$ is outside the grid, nothing happens.
• If $$$p+v_c=b$$$, $$$b+v_c$$$ is a wall cell and $$$w_c$$$ is a wall cell, nothing happens.
• If $$$p+v_c=b$$$, $$$b+v_c$$$ is a wall cell and $$$w_c$$$ is a floor cell, the player moves to $$$w_c$$$.
• if $$$p+v_c$$$ is outside the grid and $$$b+v_c$$$ is a wall cell, nothing happens.
• if $$$p+v_c$$$ is outside the grid and $$$b+v_c$$$ is outside the grid, nothing happens.
• if $$$p+v_c$$$ is outside the grid and $$$b+v_c$$$ is a floor cell, the player moves to $$$b+v_c$$$.

Note that the above are listed for covering all possibilities, but the operations are valid in only four of them (in other cases, nothing happens).

Hearthstone is one of the popular video games. Please read the following rules carefully. They are different from the usual rules.

There are $$$n$$$ kinds of secret cards numbered $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$. There are two types of events about secrets:

• add: Add a secret with an unknown number into the hero zone. No two secrets with the same number can be in the hero zone simultaneously.
• test $$$x$$$ $$$y$$$: Test whether secret $$$x$$$ exists. If secret $$$x$$$ exists, then $$$y=1$$$ and secret $$$x$$$ is removed from the hero zone; otherwise, $$$y=0$$$. Note that whatever $$$y$$$ is, secret $$$x$$$ does not exist in the hero zone after testing $$$x$$$.

An event sequence $$$E = [e_1, \ldots, e_m]$$$ is valid if and only if it is possible to assign a number from $$$1$$$ to $$$n$$$ for each add event and perform the events $$$e_1, e_2, \ldots, e_m$$$ in order such that:

• no secrets are in the hero zone at the beginning;
• secret $$$x$$$ does not exist right before an event which adds a secret $$$x$$$;
• secret $$$x$$$ exists right before an event test $$$x$$$ $$$1$$$;
• secret $$$x$$$ does not exist right before an event test $$$x$$$ $$$0$$$.

Given $$$q$$$ events $$$e_1, e_2, \ldots, e_q$$$, you need to maintain an event sequence $$$E$$$. Initially, $$$E$$$ is empty. For each $$$i = 1, 2, \ldots, q$$$ in order, try to append $$$e_i$$$ to the end of $$$E$$$. If $$$E$$$ is invalid, remove $$$e_i$$$ and report a bug. Otherwise, find the number of secrets that must exist in the hero zone and the number of secrets that must not exist in the hero zone after performing the events of $$$E$$$ in order.

Note that the number of secrets that must (not) exist is not just the number of (non-)existing secrets. For example, if $$$n = 2$$$, initially, secret 1 is missing and secret 2 is missing, so the answers would be $$$0$$$ and $$$2$$$. After a single add, secret 1 is unknown (can be or not be in hero zone) and secret 2 is unknown, so the answers are $$$0$$$ and $$$0$$$. After test $$$2$$$ $$$0$$$, secret 2 is missing, so we know the added one was certainly secret 1, so secret 1 is present, and the answers are $$$1$$$ and $$$1$$$. See examples for better understanding.

Alice and Bob invent a new game based on Texas hold'em. Please read the following rules carefully as they are different from the usual rules. The background of this problem is exactly the same as problem E.

There are $$$13$$$ ranks, which are A, K, Q, J, T, 9, 8, 7, 6, 5, 4, 3, and 2 from high to low. There are $$$4$$$ suits, which are S, H, C, and D. Every combination of a rank and a suit occurs exactly once, so there are $$$52$$$($$$=13\times 4$$$) cards.

A hand is a set of five cards. Each hand has a rank. There are $$$10$$$ types of hands. Each type also has a rank. If two hands are of different types, the hand of the type with a higher rank always ranks higher. A hand can be represented as a sequence $$$(r_1,r_2,r_3,r_4,r_5)$$$, where $$$r_i$$$ is the rank of the $$$i$$$-th card and the order of the five cards depends on the type of the hand. If two hands are of the same type, the hand represented as the lexicographically larger sequence ranks higher: formally, if we find the smallest index $$$i$$$ such that $$$r_i$$$ of two hands are different, the hand with higher $$$r_i$$$ ranks higher. If the types and the sequences $$$r$$$ of two hands are equal, two hands have the same rank.

The $$$10$$$ types are given below, from lowest to highest rank. If a hand matches the patterns of multiple types, it belongs to the one with the highest rank.

• Highcard: Any five cards. The sequence $$$r$$$ satisfies $$$r_1 \gt r_2 \gt r_3 \gt r_4 \gt r_5$$$.
• Pair: Two cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2$$$, $$$r_3 \gt r_4 \gt r_5$$$.
• Two pairs: Two cards with the same rank and another two cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2 \gt r_3=r_4$$$.
• Three of a kind: Three cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2=r_3$$$, $$$r_4 \gt r_5$$$.
• Straight: Five cards with five consecutive ranks. The sequence $$$r$$$ satisfies $$$r_1 \gt r_2 \gt r_3 \gt r_4 \gt r_5$$$. Additionally, A 2 3 4 5 is a straight, and A is regarded as a rank lower than 2 in this case. Hence A 2 3 4 5 is the straight with the lowest ranks.
• Flush: Five cards with the same suit. The sequence $$$r$$$ satisfies $$$r_1 \gt r_2 \gt r_3 \gt r_4 \gt r_5$$$.
• Full house: Three cards with the same rank and another two cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2=r_3$$$, $$$r_4=r_5$$$.
• Four of a kind: Four cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2=r_3=r_4$$$.
• Straight flush: A straight with the same suit. The sequence $$$r$$$ satisfies $$$r_1 \gt r_2 \gt r_3 \gt r_4 \gt r_5$$$. Additionally, A 2 3 4 5 with the same suit is a straight flush, and A is regarded as a rank lower than 2 in this case. Hence A 2 3 4 5 with the same suit is the straight flush with the lowest ranks.
• Royal flush: Straight flush with the ranks T, J, Q, K, and A. Four different royal flushes are of the same rank.

Two cards are dealt to each of Alice and Bob. Instead of the regular rules, $$$6$$$ community cards are dealt. Two players take community cards one by one, in turn, until each player has five cards, completing a hand. Alice takes first. The player who has a hand with higher rank wins. If two hands have same rank, there is a draw. Note that all ten cards are shown to both, and they always choose the optimal strategy.

The above are the same in problem E. The task is the following.

Given the cards of Alice, the cards of Bob and the $$$6$$$ community cards, find the winner.

Alice and Bob invent a new game based on Texas hold'em. Please read the following rules carefully as they are different from the usual rules. The background of this problem is exactly the same as problem D.

There are $$$13$$$ ranks, which are A, K, Q, J, T, 9, 8, 7, 6, 5, 4, 3, and 2 from high to low. There are $$$4$$$ suits, which are S, H, C, and D. Every combination of a rank and a suit occurs exactly once, so there are $$$52$$$($$$=13\times 4$$$) cards.

A hand is a set of five cards. Each hand has a rank. There are $$$10$$$ types of hands. Each type also has a rank. If two hands are of different types, the hand of the type with a higher rank always ranks higher. A hand can be represented as a sequence $$$(r_1,r_2,r_3,r_4,r_5)$$$, where $$$r_i$$$ is the rank of the $$$i$$$-th card and the order of the five cards depends on the type of the hand. If two hands are of the same type, the hand represented as the lexicographically larger sequence ranks higher: formally, if we find the smallest index $$$i$$$ such that $$$r_i$$$ of two hands are different, the hand with higher $$$r_i$$$ ranks higher. If the types and the sequences $$$r$$$ of two hands are equal, two hands have the same rank.

The $$$10$$$ types are given below, from lowest to highest rank. If a hand matches the patterns of multiple types, it belongs to the one with the highest rank.

• Highcard: Any five cards. The sequence $$$r$$$ satisfies $$$r_1 \gt r_2 \gt r_3 \gt r_4 \gt r_5$$$.
• Pair: Two cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2$$$, $$$r_3 \gt r_4 \gt r_5$$$.
• Two pairs: Two cards with the same rank and another two cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2 \gt r_3=r_4$$$.
• Three of a kind: Three cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2=r_3$$$, $$$r_4 \gt r_5$$$.
• Straight: Five cards with five consecutive ranks. The sequence $$$r$$$ satisfies $$$r_1 \gt r_2 \gt r_3 \gt r_4 \gt r_5$$$. Additionally, A 2 3 4 5 is a straight, and A is regarded as a rank lower than 2 in this case. Hence A 2 3 4 5 is the straight with the lowest ranks.
• Flush: Five cards with the same suit. The sequence $$$r$$$ satisfies $$$r_1 \gt r_2 \gt r_3 \gt r_4 \gt r_5$$$.
• Full house: Three cards with the same rank and another two cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2=r_3$$$, $$$r_4=r_5$$$.
• Four of a kind: Four cards with the same rank. The sequence $$$r$$$ satisfies $$$r_1=r_2=r_3=r_4$$$.
• Straight flush: A straight with the same suit. The sequence $$$r$$$ satisfies $$$r_1 \gt r_2 \gt r_3 \gt r_4 \gt r_5$$$. Additionally, A 2 3 4 5 with the same suit is a straight flush, and A is regarded as a rank lower than 2 in this case. Hence A 2 3 4 5 with the same suit is the straight flush with the lowest ranks.
• Royal flush: Straight flush with the ranks T, J, Q, K, and A. Four different royal flushes are of the same rank.

Two cards are dealt to each of Alice and Bob. Instead of the regular rules, $$$6$$$ community cards are dealt. Two players take community cards one by one, in turn, until each player has five cards, completing a hand. Alice takes first. The player who has a hand with higher rank wins. If two hands have same rank, there is a draw. Note that all ten cards are shown to both, and they always choose the optimal strategy.

The above are the same in problem D. The task is the following.

Given the cards of Alice and the cards of Bob, find possible $$$6$$$ community cards such that Alice wins, that Bob wins, and that there is a draw.

Given a sequence $$$s$$$ of length $$$n$$$ and a sequence $$$t$$$ of length $$$m$$$, find the length of the longest common subsequence of $$$s$$$ and $$$t$$$.

Consider $$$a$$$ and $$$p$$$, two permutations of length $$$n$$$. Initially, $$$a_i=p_i=i$$$ for all $$$1\le i\le n$$$. Let $$$A$$$ be a sequence of permutations such that $$$A_1=a$$$ and $$$A_{i,j}=A_{i-1,p_j}$$$ for all $$$i\ge 1$$$ and $$$1\le j\le n$$$.

There are three types of operations, where $$$x$$$ and $$$y$$$ are positive integers:

1. swap_a $$$x$$$ $$$y$$$: swap $$$a_x$$$ and $$$a_y$$$, where $$$1\le x, y\le n$$$;
2. swap_p $$$x$$$ $$$y$$$: swap $$$p_x$$$ and $$$p_y$$$, where $$$1\le x, y\le n$$$;
3. cmp $$$x$$$ $$$y$$$: compare $$$A_x$$$ with $$$A_y$$$ lexicographically.

For each operation of type 3, output the relationship between $$$A_x$$$ and $$$A_y$$$. A permutation $$$s$$$ is lexicographically smaller than a permutation $$$t$$$ if and only if there exists an index $$$i$$$ such that $$$s_i \lt t_i$$$ and $$$s_j=t_j$$$ for all $$$1\le j \lt i$$$.

Expression evaluation is a classic problem. In this problem, you only need to evaluate an expression of length less than $$$10^5$$$. It may only contain non-negative integers (possibly with leading zeros), and also operations '+', '-', and '*'. Formally, it satisfies the following grammar:

For example, 013, 0213-2132*0213 are valid, but -2132 and 32113+-3213 are invalid.

The result of the evaluation may be too large or negative. Output the result modulo $$$2^{32}$$$ to avoid overflow since you will use a custom $$$32$$$-bit machine to evaluate the expression.

The $$$32$$$-bit machine contains $$$2^{10}$$$ units of memory, denoted as $$$r[0], r[1], \ldots, r[2^{10}-1]$$$. Each unit is a $$$32$$$-bit unsigned integer, also working as an instruction. The machine's input is an expression described above, and the machine's output is the value of that expression modulo $$$2^{32}$$$.

In each cycle, let $$$pc=r[0]\bmod 2^{10}$$$. The machine executes the instruction $$$r[pc]$$$. Consider the expansion $$$r[pc]=a2^{30}+b2^{20}+c2^{10}+d$$$ at the beginning of cycle, where $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ are non-negative integers less than $$$2^{10}$$$:

• If $$$a=0$$$, the machine outputs the value of $$$r[b]$$$ and stops.
• If $$$a=1$$$, and then:
  • If there are no characters in input left, set $$$r[0]$$$ to $$$r[d]$$$;
  • Otherwise, set $$$r[b]$$$ to the ASCII code of the next character of input, and then set $$$r[0]$$$ to $$$r[c]$$$.
• If $$$a=2$$$, set $$$r[b]$$$ to $$$(r[b]+r[c])\bmod 2^{32}$$$, and then set $$$r[0]$$$ to $$$r[d]$$$.
• If $$$a=3$$$, and then:
  • If $$$r[b]=0$$$, set $$$r[0]$$$ to the value of $$$r[c]$$$;
  • Otherwise, set $$$r[0]$$$ to the value of $$$r[d]$$$.

You need to set the initial value for each unit of memory so that, for any expression possible within the constraints, the machine can stop after a finite amount of cycles and output the result of the expression modulo $$$2^{32}$$$.

Since there is a time limit for testing, in this problem, the machine can execute at most $$$10^8$$$ cycles.

Two undirected graphs of size $$$n$$$ are equivalent in connectivity when there is a path from $$$u$$$ to $$$v$$$ in one graph if and only if there is a path from $$$u$$$ to $$$v$$$ in the other graph for all $$$1\le u \lt v\le n$$$.

Given is a sequence of $$$k$$$ graphs $$$G_1, G_2, \ldots, G_k$$$. Each graph is of size $$$n$$$. In this sequence, for each $$$i = 2, 3, \ldots, k$$$, there exists $$$p_i \lt i$$$ such that $$$G_i$$$ can be obtained from $$$G_{p_i}$$$ by adding or removing an edge. Divide the given graphs into groups: two graphs must be in the same group if and only if they are equivalent in connectivity.

Given a tree with $$$n$$$ vertices, for each node $$$i = 1, 2, \ldots, n$$$, find an integer point $$$p_i = (x_i, y_i)$$$, and then, for each edge $$$(u, v)$$$, connect points $$$p_u$$$ and $$$p_v$$$ with a line segment, so that the following conditions hold:

1. No two points coincide.
2. No two line segments have common points except at both endpoints.
3. There exists a line such that the shape formed by the points is symmetric about the line and the shape formed by the line segments is symmetric about the line.

Given is a strictly convex polygon with $$$n$$$ vertices $$$p_1, p_2, \ldots, p_n$$$ in counterclockwise. Denote $$$C_i$$$ as the polygon with $$$i$$$ vertices $$$p_1, p_2, \ldots, p_i$$$. For each $$$i=3, 4, \ldots, n$$$, find the lines which $$$C_i$$$ is symmetric about.

A point set $$$S$$$ is symmetric about a line $$$\ell$$$ if and only if there exists $$$s' \in S$$$ satisfying that $$$s'$$$ and $$$s$$$ are symmetric about the line $$$\ell$$$ for all $$$s \in S$$$.

Let us denote the distance between two points $$$a$$$ and $$$b$$$ as $$$d(a,b)$$$. The distance between two non-empty point sets $$$A$$$ and $$$B$$$ is $$$\inf \left\{d(a,b) : a \in A, \, b \in B \right\}$$$. The infimum of a non-empty real number set $$$S$$$ is the maximum value of $$$x$$$ which satisfies $$$x \le s$$$ for all $$$s \in S$$$.

Lines $$$\ell_1, \ell_2, \ldots, \ell_n$$$ are given, where two or more lines may coincide. For a point $$$s$$$, define $$$C(s)$$$ as the intersection of all sets $$$S$$$ satisfying $$$s \in S$$$ such that $$$S$$$ is symmetric about $$$\ell_i$$$ for all $$$i = 1, 2, \ldots, n$$$.

There are $$$q$$$ queries. For each query, given two points $$$A$$$ and $$$B$$$, find the distance between $$$C(A)$$$ and $$$C(B)$$$.