You are given an array $$$a$$$ of length $$$n$$$. For each $$$k=1,2,\ldots,n$$$, consider the following process independently.

Initially, the array is $$$a$$$. You must perform exactly $$$k$$$ operations. In each operation, you may choose one of the following two actions:

• Backspace: remove the first element of the current array;
• Delete: remove the last element of the current array.

Your score is defined as the value of the element removed in the $$$k$$$-th operation.

For each $$$k=1,2,\ldots,n$$$, find the maximum score you can obtain.

Alice and Bob are playing a game on a permutation, with Alice moving first.

A sequence of length $$$n$$$ is called a permutation if and only if each integer from $$$1,2,\dots,n$$$ appears exactly once in the sequence.

Initially, a permutation $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$ is given. At any moment during the game, the current sequence is always a permutation of some length $$$m$$$. Alice and Bob take turns performing exactly one of the following two operations:

- Choose an index $$$i$$$ $$$(1\le i \lt m)$$$ such that $$$a_i \gt a_{i+1}$$$, and swap $$$a_i$$$ and $$$a_{i+1}$$$.

- Choose an index $$$i$$$ $$$(1\le i \lt m)$$$ such that $$$a_{i+1}=a_i+1$$$, and delete $$$a_i$$$ and $$$a_{i+1}$$$. Then renumber the remaining elements according to their relative order: the $$$k$$$-th smallest remaining element is renumbered as $$$k$$$, so that the remaining sequence becomes a permutation again.

For example, suppose the current permutation is $$$[2,3,4,1]$$$. The adjacent elements $$$2$$$ and $$$3$$$ can be deleted, leaving $$$[4,1]$$$; after renumbering, the permutation becomes $$$[2,1]$$$.

A player who cannot perform any operation loses the game. Assuming that both Alice and Bob play optimally, determine the winner.

You are given an integer array $$$a$$$ of length $$$n$$$.

In one operation, you may choose two distinct indices $$$i,j$$$ satisfying

$$$$$$ 1\le i,j\le n,\qquad i\ne j, $$$$$$

and perform the following changes simultaneously:

$$$$$$ a_i\gets a_i+3,\qquad a_j\gets a_j-1. $$$$$$

You may perform any finite number of operations, including zero operations. The elements of the array are allowed to become negative during the process.

The range of an array is defined as

$$$$$$ \max_i a_i-\min_i a_i. $$$$$$

Find the minimum possible range of the array after performing any number of operations.

There are $$$n$$$ resonators placed in order along a corridor. The current frequency offset of the $$$i$$$-th resonator is $$$a_i$$$, and its target offset is $$$b_i$$$.

The tuning device can only be activated from one end of the corridor. In one operation, you may choose any nonzero integer $$$x$$$ and perform one of the following operations:

1. Choose $$$k$$$ $$$(1\le k\le n)$$$ and add $$$x$$$ to every number in the prefix $$$a_1,a_2,\ldots,a_k$$$;
2. Choose $$$k$$$ $$$(1\le k\le n)$$$ and add $$$x$$$ to every number in the suffix $$$a_k,a_{k+1},\ldots,a_n$$$.

$$$x$$$ may be positive or negative. Regardless of the magnitude of $$$|x|$$$, the modification counts as exactly one operation.

Find the minimum number of operations required to transform sequence $$$a$$$ into sequence $$$b$$$.

This is an interactive problem.

There is an unknown sequence $$$B$$$ consisting of $$$0$$$s and $$$1$$$s, with 1-based indexing. You can make multiple queries. In each query, you specify a center $$$m$$$ and a radius $$$r$$$, and the interactor will return the number of $$$1$$$s in the punctured neighborhood of indices $$$[m-r,m+r]\setminus\{m\}$$$ of $$$B$$$. Try to determine the total number of $$$1$$$s in $$$B$$$.

Note that the interval you query must not exceed the boundaries of the sequence itself.

There are multiple test cases in this problem.

First, read a line containing a single positive integer $$$T$$$ $$$(1\le T\le1000)$$$, denoting the number of test cases.

For each test case:

• First read a line containing a single integer $$$n$$$ $$$(4\le n\le1000)$$$, denoting the length of $$$B$$$.
• To make a query, output a line in the format ? m r and flush the output buffer. It is required that $$$2\le m\le n-1,r\ge1,m-r\ge1,m+r\le n$$$. Then, read a line containing a non-negative integer, denoting the value of $$$\sum_{i=1}^r(B_{m-i}+B_{m+i})$$$.
• When you have found the answer, output a line in the format ! x and flush the output buffer, where $$$x$$$ represents the total number of $$$1$$$s in $$$B$$$.
• As an exception, if it is impossible to determine the answer no matter how queries are made, output a line ! -1 and flush the output buffer.

The number of queries for each test case must not exceed $$$35$$$.

Violations such as an incorrect interaction format or exceeding the query limit will result in an undefined verdict.

Given an integer $$$n$$$, construct a permutation $$$p_1,p_2,\ldots,p_n$$$ of $$$1,2,\ldots,n$$$ such that the sum of every pair of adjacent elements is not a perfect square. In other words, for every $$$1\le i \lt n$$$, there does not exist an integer $$$x$$$ such that

$$$p_i+p_{i+1}=x^2$$$.

It can be proven that an answer exists for every valid $$$n$$$.

This is a communication problem.

In this problem, your program will be run twice. Between the two runs, all variables stored in memory will be lost, but the information obtained during the first run may be crucial for solving the problem during the second run.

There are two characters in this problem: "Nailoong" and "Bombloong".

Nailoong has complete structural information about a tree with $$$n$$$ vertices, while Bombloong only knows the number of vertices $$$n$$$. Since Bombloong has been imprisoned by the evil little leopard, Nailoong can only help Bombloong reconstruct a tree that is isomorphic to the original tree through a special one-way communication method.

Two trees $$$T_1(V_1,E_1)$$$ and $$$T_2(V_2,E_2)$$$ are called isomorphic if and only if there exists a bijection $$$f:V_1\to V_2$$$ such that for every $$$\{u,v\}\in E_1$$$, $$$\{f(u),f(v)\}\in E_2$$$.

The rules of communication are as follows:

• Nailoong must color every vertex of the tree either black, white, or grey;
• the little leopard generates a sequence according to the code below;
• Nailoong can send only the sequence $$$c_1,c_2,\dots,c_{2n-1}$$$ of length $$$2n-1$$$ to Bombloong.

function DFS(u, parent)
    append u to tour
    for v in vertices adjacent to u
        if v is not parent, then
            DFS(v, u)
            append u to tour
        Endif
    Endfor
Endfunction

function GenerateSequence(T, color)
    tour <- empty sequence
    root <- the starting vertex chosen by the leopard
    DFS(root, NIL)
    c <- empty sequence
    for v in tour
        append color[v] to c
    Endfor
    Return c
Endfunction

Nailoong cannot directly send the vertex indices to Bombloong; she can only send the sequence $$$c$$$. After receiving $$$n$$$ and the sequence $$$c$$$, Bombloong must construct and output a tree isomorphic to Nailoong's tree.

Communication Protocol

In each test, the contestant's program will be run twice. A testing tool is provided in the handout files for local debugging.

First Run

In the first run, you play the role of "Nailoong".

Input

The first line contains a string first, which allows your program to identify that this is the first run.

The second line contains an integer $$$T$$$ $$$(1\le T\le10^4)$$$, the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(2\le n\le2\times10^5)$$$, the number of vertices in the tree.

The next $$$n-1$$$ lines each contain two integers $$$u,v$$$ $$$(1\le u,v\le n)$$$, denoting an edge of the tree.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \times 10^5$$$.

Output

Your output should contain $$$T$$$ lines. The $$$i$$$-th line contains a sequence $$$col_1,col_2,\dots,col_n$$$ of length $$$n$$$, where each $$$col_i\in\{\mathbf{0,1,2}\}$$$ $$$(i=1,2,\dots,n)$$$, denoting the color assigned by Nailoong to the $$$i$$$-th vertex. $$$col_i=0$$$ denotes white, $$$col_i=1$$$ denotes black, and $$$col_i=2$$$ denotes grey.

Second Run

In the second run, you play the role of "Bombloong".

Input

The first line contains a string second, which allows your program to identify that this is the second run.

The second line contains an integer $$$T$$$ $$$(1\le T\le10^4)$$$, the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(2\le n\le2\times10^5)$$$, the number of vertices in the tree.

The next line contains $$$2n-1$$$ integers $$$c_1,c_2,\dots,c_{2n-1}$$$, denoting the sequence generated by the judge according to Nailoong's coloring.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \times 10^5$$$.

Output

For the $$$i$$$-th test case, let the input number of vertices be $$$n$$$.

Output $$$n-1$$$ lines, each containing two integers $$$u,v$$$ $$$(1\le u,v\le n)$$$, denoting an edge of the reconstructed tree.

You must ensure that the output tree is isomorphic to the tree given in the first run.

This is a communication problem.

In this problem, your program will be run twice. Between the two runs, all variables stored in memory will be lost, but the information obtained during the first run may be crucial for solving the problem during the second run.

There are two characters in this problem: "Nailoong" and "Bombloong".

Nailoong has complete structural information about a tree with $$$n$$$ vertices, while Bombloong only knows the number of vertices $$$n$$$. Since Bombloong has been imprisoned by the evil little leopard, Nailoong can only help Bombloong reconstruct a tree that is isomorphic to the original tree through a special one-way communication method.

Two trees $$$T_1(V_1,E_1)$$$ and $$$T_2(V_2,E_2)$$$ are called isomorphic if and only if there exists a bijection $$$f:V_1\to V_2$$$ such that for every $$$\{u,v\}\in E_1$$$, $$$\{f(u),f(v)\}\in E_2$$$.

The rules of communication are as follows:

• Nailoong must color every vertex of the tree either black or white;
• the little leopard generates a sequence according to the code below;
• Nailoong can send only the sequence $$$c_1,c_2,\dots,c_{2n-1}$$$ of length $$$2n-1$$$ to Bombloong.

function DFS(u, parent)
    append u to tour
    for v in vertices adjacent to u
        if v is not parent, then
            DFS(v, u)
            append u to tour
        Endif
    Endfor
Endfunction

function GenerateSequence(T, color)
    tour <- empty sequence
    root <- the starting vertex chosen by the leopard
    DFS(root, NIL)
    c <- empty sequence
    for v in tour
        append color[v] to c
    Endfor
    Return c
Endfunction

Nailoong cannot directly send the vertex indices to Bombloong; she can only send the sequence $$$c$$$. After receiving $$$n$$$ and the sequence $$$c$$$, Bombloong must construct and output a tree isomorphic to Nailoong's tree.

Communication Protocol

In each test, the contestant's program will be run twice. A testing tool is provided in the handout files for local debugging.

First Run

In the first run, you play the role of "Nailoong".

Input

The first line contains a string first, which allows your program to identify that this is the first run.

The second line contains an integer $$$T$$$ $$$(1\le T\le10^4)$$$, the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(2\le n\le2\times10^5)$$$, the number of vertices in the tree.

The next $$$n-1$$$ lines each contain two integers $$$u,v$$$ $$$(1\le u,v\le n)$$$, denoting an edge of the tree.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \times 10^5$$$.

Output

Your output should contain $$$T$$$ lines. The $$$i$$$-th line contains a sequence $$$col_1,col_2,\dots,col_n$$$ of length $$$n$$$, where each $$$col_i\in\{\textbf{0},\textbf{1}\}$$$ $$$(i=1,2,\dots,n)$$$ denotes the color assigned by Nailoong to the $$$i$$$-th vertex.$$$col_i=0$$$ denotes white, and $$$col_i=1$$$ denotes black.

Second Run

In the second run, you play the role of "Bombloong".

Input

The first line contains a string second, which allows your program to identify that this is the second run.

The second line contains an integer $$$T$$$ $$$(1\le T\le10^4)$$$, the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(2\le n\le2\times10^5)$$$, the number of vertices in the tree.

The next line contains $$$2n-1$$$ integers $$$c_1,c_2,\dots,c_{2n-1}$$$, denoting the sequence generated by the judge according to Nailoong's coloring.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \times 10^5$$$.

Output

For the $$$i$$$-th test case, let the input number of vertices be $$$n$$$.

Output $$$n-1$$$ lines, each containing two integers $$$u,v$$$ $$$(1\le u,v\le n)$$$, denoting an edge of the reconstructed tree.

You must ensure that the output tree is isomorphic to the tree given in the first run.

You are given a weighted tree with $$$n$$$ vertices, rooted at vertex $$$1$$$.

Vertex $$$i$$$ has a frequency band $$$c_i$$$ and a transmission time $$$a_i$$$. Each frequency band $$$c$$$ has an importance value $$$w_c$$$.

For two distinct vertices $$$u,v$$$ using the same frequency band, define their synchronization cost as

$$$$$$ D(u,v)=|a_u-a_v|+\operatorname{dist}(u,v), $$$$$$

where $$$\operatorname{dist}(u,v)$$$ denotes the sum of edge weights on the simple path between vertices $$$u$$$ and $$$v$$$.

There are $$$q$$$ queries. Each query gives a vertex $$$x$$$ and a non-negative integer $$$K$$$.

We say that a frequency band $$$c$$$ produces an echo in the subtree of $$$x$$$ if and only if there exist two distinct vertices

$$$$$$ u,v\in\operatorname{subtree}(x) $$$$$$

such that

$$$$$$ c_u=c_v=c $$$$$$

and

$$$$$$ D(u,v)\le K. $$$$$$

Here, $$$\operatorname{subtree}(x)$$$ denotes the subtree rooted at $$$x$$$.

For each query, find the sum of the importance values of all frequency bands that produce an echo, i.e.

$$$$$$ \sum_{c=1}^{m} w_c \left[ \exists\,u\ne v\in\operatorname{subtree}(x),\ c_u=c_v=c,\ D(u,v)\le K \right]. $$$$$$

The square brackets denote the Iverson bracket: its value is $$$1$$$ if the condition inside is true, and $$$0$$$ otherwise.

Given a 1-indexed string $$$s$$$ of length $$$n$$$. For each $$$1\le i\le n$$$, a non-negative integer $$$r$$$ is called a palindromic radius of center $$$i$$$ if the substring of length $$$2r+1$$$ centered at $$$i$$$ is a palindrome.

For each center $$$i$$$, find the palindromic radius such that the corresponding palindromic substring is lexicographically smallest.

You are given two coprime positive integers $$$p$$$ and $$$q$$$. There are $$$pq$$$ different types of cards, numbered $$$0,1,\ldots,pq-1$$$.

There are two types of standard card packs:

• Type-1 standard card packs: there are $$$p$$$ kinds, numbered by $$$u$$$ ($$$0\le u \lt p$$$). The pack numbered $$$u$$$ contains one copy of every card whose number satisfies $$$x\equiv u\pmod p$$$ (so each pack contains exactly $$$q$$$ cards).
• Type-2 standard card packs: there are $$$q$$$ kinds, numbered by $$$v$$$ ($$$0\le v \lt q$$$). The pack numbered $$$v$$$ contains one copy of every card whose number satisfies $$$x\equiv v\pmod q$$$ (so each pack contains exactly $$$p$$$ cards).

There are now $$$n$$$ cards arranged on the table, where the number of the $$$i$$$-th card is $$$a_i$$$. You need to process $$$Q$$$ operations of the following two types:

• 1 i x: replace the number of the $$$i$$$-th card with $$$x$$$.
• 2 l r: determine whether all cards in the interval $$$[l,r]$$$ can be partitioned exactly into several standard card packs.

Note: When repacking the cards, every card in the interval must belong to exactly one pack, and each kind of standard card pack may be used any number of times.

Given a deterministic finite automaton (DFA) with a state set $$$Q=\{1,2,\dots,n\}$$$, a start state $$$q=1$$$, an accept state set $$$F$$$ of size $$$m$$$, and an alphabet $$$\Sigma=\{\texttt{A},\texttt{C}\}$$$. Find the lexicographically smallest string accepted by the automaton with a length of at least $$$k$$$. Since the answer might be very long, if the length of the answer exceeds $$$n$$$, you only need to output the last $$$n$$$ characters of the answer. If no string satisfies the aforementioned requirements, output WA.

A string is accepted by the automaton if and only if there exists a walk starting from the initial state and ending at an accept state, such that the letters on the traversed transition edges exactly form the string. The walk can pass through repeated vertices and edges.

You are given an integer $$$n$$$, an integer $$$k$$$, and an integer $$$p$$$.

Consider all functions $$$$$$ f:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}. $$$$$$

Let $$$f^k$$$ denote the $$$k$$$-fold iteration of $$$f$$$. If $$$x \in \{1, 2, \dots, n\}$$$ satisfies $$$f^k(x) = x$$$, then $$$x$$$ is called a fixed point of $$$f^k$$$.

Find the number of functions $$$f$$$ that have exactly $$$p$$$ fixed points under $$$f^k$$$. Output the answer modulo $$$10^9+7$$$.