Hello codeforces!

CSP-J/S(Certified Software Professional-Junior/Senior) of China ended. CSP-J/S (or you can say NOIp ,but it has been dead) was held by OI rules. In OI rules, every problem has the same score distribution $$$100$$$ points. In one problem, there is several testdatas (like $$$10$$$ ,$$$20$$$ or $$$25$$$). Every testdata has the same score distributions. Once you pass a testdata, you can get the score. You can submit your code during the contest, but can't see the result. The organizer will judge all the programs together after contest.

I'd like to share the problems of CSP-S here! Hope you guys enjoy. Don't mind my poor English, I spent a whole afternoon translating.

**D1T1 code**

$$$\bf{D1T1\ Gray\ Code\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

*Gray Code* is a special permutation of $$$n$$$-bit binary strings ,which requires adjacent strings have **exactly one different** bit. Specially, the first string is adjacent to the last string.

One example of $$$2$$$-bit *Gray Code* is $$$00,01,11,10$$$.

We give an algorithm of generating *Gray Code* below:

$$$1.$$$ $$$1$$$-bit

*Gray Code*consist of two $$$1$$$-bit binary string: $$$0,1$$$$$$2.$$$ The first $$$2^n$$$ binary strings of $$$(n+1)$$$-bit

*Gray Code*is $$$n$$$-bit*Gray Code*($$$2^n$$$ binary strings in total) generated by this algorithm adding a prefix $$$0$$$.- $$$3.$$$ The next $$$2^n$$$ binary strings of $$$(n+1)$$$-bit
*Gray Code*is $$$n$$$-bit*Gray Code*($$$2^n$$$ binary strings in total) generated by this algorithm**being reversed**,then adding a prefix $$$1$$$.

We number all the *Gray Code* from $$$0$$$ to $$$2^n-1$$$. Now you task is to figure out the $$$k$$$-th binary string of $$$n$$$-bit *Gray Code*.

$$$\bf{Input}$$$

Only two integer $$$n ,k$$$ ,the bit of *Gray Code* and the index of the binary string.

$$$\bf{Output}$$$

One binary string, the answer.

$$$\bf{Constraints}$$$

$$$1\le n \le 64, 0\le k < 2^n$$$

**D1T2 brackets**

$$$\bf{D1T2\ Brackets\ Tree\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

First we have some definitions in this problem.

What is a **valid bracket string**:

- $$$1.$$$ $$$()$$$ is;
- $$$2.$$$ If $$$A$$$ is, then $$$(A)$$$ is;
- $$$3.$$$ if $$$A$$$ and $$$B$$$ are, then $$$(AB)$$$ is.

What are a **substring** and **different substrings**:

- $$$1.$$$ The substring of string $$$S$$$ is a string consisting of any continuous characters in string $$$S$$$. We can describe a substring like $$$S(l,r)\ (1 \le l \le r \le |S| ,|S|$$$ is the length of string $$$S$$$) , where $$$l$$$ and $$$r$$$ are the left endpoint and right endpoint, respectively.
- $$$2.$$$ Two substrings of string $$$S$$$ is regarded different when they have different $$$l$$$ or $$$r$$$.

A tree consists of $$$n$$$ vertices and $$$n-1$$$ edges. Every edge connects two vertices. There is **exactly one** simple path between two vertices on a tree.

Little Q is a curious kid. One day on his way to school he saw a tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The vertex with index $$$1$$$ is the root. Except vertex $$$1$$$, every vertex has one parent. The parent of vertex $$$u$$$ is $$$f_u\ (1 \le f_u < u)$$$.

Little Q found that there was **exactly one** bracket on a vertex. It could be $$$'('$$$ or $$$')'$$$. Little Q defined $$$s_i$$$ as the string formed by: writing down all the vertices through the simple path from root to vertex $$$i$$$ in one line.

It is obvious that $$$s_i$$$ is a bracket string but may not be a valid bracket string. So Little Q was going to figure out, for every $$$i\ (1 \le i \le n)$$$, how many **different substrings** of $$$s_i$$$ are **valid bracket string**?

This problem is so difficult for Little Q, so he wants you to help him out. Denote $$$k_i$$$ is the number of valid bracket string in different substrings of $$$s_i$$$. You need to figure out $$$\bigotimes\limits^{n}_{i=1} i\times k_i$$$. $$$\bigotimes$$$ stands for $$$\bf{xor}$$$ operation here.

$$$\bf{Input}$$$

The first line contains one integer $$$n$$$, the number of vertices on the tree.

The second line contains one string consisting of characters $$$'(’$$$ and $$$')'$$$ (No quotation marks). The $$$i$$$-th bracket is the bracket on $$$i$$$-th vertex.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

One integer, the answer.

$$$\bf{Constrains}$$$

$$$1 \le n \le 5\times 10^5$$$

**D1T3 tree**

$$$\bf{D1T3\ Numbers\ on\ a\ Tree\ 2s\ 256MB}$$$

$$$\bf{Statement}$$$

You are given a tree consisting of $$$n$$$ vertices and $$$n-1$$$ edges. Vertices are numbered from $$$1$$$ to $$$n$$$. At the beginning, every vertex has a **different number** on it. Numbers are $$$1,2,...,n$$$.

Next, you are going to cut off **exactly** $$$n-1$$$ edges. During one operation, you choose a edge connecting vertex $$$u ,v$$$, exchange each number on itself, then the edge disappears.

After $$$n-1$$$ operations, all the edges are cut off. Now sort all the vertices by number on it, from small to large. Then you get a permutation $$$P_i$$$ of the vertices. Your goal is to minimize the lexicographical order of $$$P_i$$$.

$$$\bf{Input}$$$

**Input contains several testcases.**

The first line contains an integer $$$T$$$, the number of testcases.

For every testcases:

The first line contains an integer $$$n$$$, the number of vertices.

The second line contains $$$n$$$ integers, the $$$i$$$-th integer is the index of the vertex on which number $$$i$$$ is at beginning.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

For every testcase:

Output $$$n$$$ integers separated by space, the minimum lexicographical order of permutation $$$P_i$$$.

$$$\bf{Constraints}$$$

$$$1 \le T \le 10 ,1 \le n \le 2000$$$

**D2T1 meal**

$$$\bf{D2T1\ Today's\ Meal\ of\ Emiya's\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

Emiya is a high school student. He is good at cooking. He masters $$$n$$$ ways of cooking and has $$$m$$$ kinds of different ingredients. We number cooking ways from $$$1$$$ to $$$n$$$ and ingredients from $$$1$$$ to $$$m$$$.

Every dish Emiya makes will use **exactly one** cooking way and **exactly one** ingredient. If he use $$$i$$$-th cooking way and $$$j$$$-th ingredient, then he can make $$$a_{i,j}$$$ different dishes, which means Emiya can make $$$\sum\limits^{n}_{i=1}\sum\limits^{m}_{j=1}a_{i,j}$$$ different dishes in total.

Today Emiya is going to make a meal for his friend Yazid and Rin. They all have their own needs. For a meal with $$$k$$$ dishes:

- Emiya does not want to make themselves hungry, so $$$k\ge 1$$$.
- Rin wants to try different cooking ways, so every dishes must use
**different**cooking ways. - Yazid does not want to taste many dishes made of the same ingredient, so all the ingredients can be used in
**at most**$$$\left\lfloor \frac{k}{2}\right\rfloor$$$ dishes.

$$$\left\lfloor x\right\rfloor$$$ here means the minimum integer that is equal or less than $$$x$$$.

Their needs is easy to realize for Emiya, so he tries to figure out how many ways there are to make a meal? Two meals are different when they have at least one different dish.

Emiya finds you. You should help him calculate the number of ways modulo $$$998,244,353$$$

$$$\bf{Input}$$$

The first line contains two integer $$$n,m$$$, the number of cooking ways and the number of different ingredients.

In the next $$$n$$$ lines ,the $$$j$$$-th number of $$$i$$$-th line is $$$a_{i,j}$$$, the different dishes Emiya can make when using $$$i$$$-th cooking way and $$$j$$$-th ingredient.

$$$\bf{Output}$$$

One integer, the answer modulo $$$998,244,353$$$.

$$$\bf{Constraints}$$$

$$$1 \le n \le 100 ,1 \le m \le 2000 ,0 \le a_{i,j} < 998,244,353$$$

**D2T2 partition**

$$$\bf{D2T2\ Partition\ 2s\ 1GB}$$$

$$$\bf{Statement}$$$

In 2048, in the exam hall of The 48th CSP, contestant Little Ming is looking at the first problem. The sample has $$$n$$$ testcases numbered from $$$1$$$ to $$$n$$$. The scale of $$$i$$$-th testcase is $$$a_i$$$.

Little Ming does a brute-force solution. His program needs $$$u^2$$$ seconds to solve a testcases with $$$u$$$ scale. However, after running on a testcases with $$$u$$$ scale, the program will get RE on any testcases with scale **strictly less** than $$$u$$$. In the sample, $$$a_i$$$ is not always increasing. Little Ming wants to get AC on the sample without reprogramming ,so he use a very natural way: combining some **adjacent** testcases. The new scale of some combined testcases is **the sum** of scale of these testcases.

Formally, Little Ming needs to find out some borders $$$1 \le k_1 < k_2 < ... <k_p \le n$$$, making:

When $$$p = 0$$$, it means Little Ming combines all testcases together.

Little Ming does not want to get RE or TLE, so he wants to minimum his program's running time, which means **minimizing**:

Little Ming loves the problem very much, so he writes this problem and ask you: with given $$$n$$$ and $$$a_i$$$, how to figure out the minimum running time?

$$$\bf{Input}$$$

**To avoid much input time, some testcases will be generated in contestants' program**.

The first line contains two integer $$$n,type$$$ ,the number of "testcases" and the way of inputting.

- $$$1.$$$ If $$$type = 0$$$, $$$a_i$$$ will be given directly. The second line contains $$$n$$$ integers $$$a_i$$$ separated by space, the scale of every "testcases".
- $$$2.$$$ If $$$type = 1$$$, $$$a_i$$$ will be generated specially, the way of generating is written below. The second line contains six integers $$$x,y,z,b_1,b_2,m$$$. In the next $$$m$$$ line, the $$$i$$$-th line contains three integers $$$p_i,l_i,r_i$$$.

$$$type = 2$$$ only appear on testcases $$$23,24,25$$$. The way of generating is:

Guarantee that $$$n\ge 2$$$. If $$$n>2$$$ ,then $$$\forall\ 3\le i\le n,b_i=(x\times b_{i-1} +y \times b_{i-2} + z) \mod 2^{30}$$$

Guarantee that $$$1 \le p_i \le n ,p_m = n ,p_0 = 0$$$ and $$$\forall\ 0 \le i < m,p_i<p_{i+1}$$$.

For all $$$1 \le j \le m$$$ ,if index $$$i(1 \le i \le n)$$$ satisfies $$$p_{j-1} < i \le p_j$$$, then $$$a_i=(b_i\mod (r_j-l_j+1)) + l_j$$$.

**The ways of generating is just to reduce the input time. Standard solution does not rely on it.**

$$$\bf{Output}$$$

One integer, the answer.

$$$\bf{Constraints}$$$

The problem has $$$25$$$ testcases.

For testcases $$$1\sim 22,2 \le n \le 5 \times10^5,1\le a_i \le 10^6,type=0$$$.

For testcases $$$23\sim25,2 \le n \le 4\times 10^7,1 \le a_i \le 10^9 ,1\le m\le 10^5 ,1 \le l_i \le r_i\le 10^9,0 \le x,y,z,b_1,b_2 < 2^{30},type=1$$$

**D2T3 centroid**

$$$\bf{D2T3\ The\ Centroid\ of\ a\ Tree\ 3s\ 256MB}$$$

Little Simple is learning discrete mathematics! It's about graph theory today! He makes two notes in class:

- $$$1.$$$ On a tree with $$$n$$$ vertices, there are $$$n-1$$$ undirected edges. There is
**exactly one**simple path between two vertices. Delete a vertex and all edges that connect it, and the tree splits into several sub-trees; delete an edge(not delete vertex it connects, the same below), and the tree splits into**exactly two**sub-trees. - $$$2.$$$ For a tree with $$$n$$$ vertices and a vertex $$$c$$$, we call vertex $$$c$$$ the
**centroid**of the tree if after deleting vertex $$$c$$$ ,the vertex numbers of the left trees are all**less than**$$$\left\lfloor \frac{n}{2} \right\rfloor$$$($$$\left\lfloor x \right\rfloor$$$ here means floor function). For those tree whose vertices is more than one, the number of centroid is only $$$1$$$ or $$$2$$$.

After class, the teacher gives Little Simple a tree $$$S$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. It is Little Simple's homework to figure the sum of two splitting subtrees when cutting every edge, respectively, which is:

In the formula above, $$$E$$$ is the edge set of tree $$$S$$$, $$$(u ,v)$$$ is a edge that connects vertex $$$u$$$ and vertex $$$v$$$. $$$S'_u$$$ and $$$S'_v$$$ are two sub-tree into which tree $$$S$$$ is split after deleting edge $$$(u ,v)$$$.

Little Simple does not think his homework is simple, so he asks you for help.

$$$\bf{Input}$$$

**Input contains several testcases**

The first line contains a integer $$$T$$$, the number of testcases.

For every testcase:

The first line contains a integer $$$n$$$, the number of vertices.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

For every testcase:

Output one integer, the answer.

$$$\bf{Constrains}$$$

$$$1 \le T \le 5,1 \le n \le 299995$$$