Theforces Round #34 (ABC-Forces)
A. An OK Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an $$$n \times m$$$ grid. At first, all cells are white.

An "O" is a set of $$$10$$$ red cells with the following shape:

A "K" is a set of $$$8$$$ blue cells with the following shape:

Note: You cannot rotate or flip these two shapes.

Count different coloring schemes containing exactly $$$10$$$ red and $$$8$$$ blue cells, so that the grid contains exactly one "O" and one "K".

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$).

The only line of each testcase contains two space-separated integers $$$n,m$$$ ($$$1 \le n,m \le 50$$$).

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases does not exceed $$$50$$$, respectively.

Output

For each test case, output a single integer, which is the number of different coloring schemes where exactly one "O" and one "K" can be placed in the grid.

Example
Input
5
4 6
1 1
5 7
7 5
11 22
Output
2
0
24
0
21464
Note

In the first case, the two schemes are shown below.

B. A Cool Pair Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$.

For the integer $$$n$$$, a pair $$$(a,b)$$$ is considered cool only if:

  • $$$1 \le a \lt b \le n$$$;
  • $$$a$$$ $$$\&$$$ $$$b$$$ $$$=$$$ $$$0$$$, where $$$\&$$$ denotes the bitwise AND operation.

For a given integer $$$n$$$, find the maximum value of $$$a \cdot b$$$ among all cool pairs $$$(a, b)$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of test cases.

For each test case, the only line contains a single integer $$$n$$$$$$(2 \le n \le 10^9)$$$.

Output

For each test case, print the maximum value of $$$a \cdot b$$$ for all cool pairs $$$(a, b)$$$.

Example
Input
4
2
9
996
1000000000
Output
2
56
261632
288230375614840832

C. Yet Another Cool Pair Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$.

For the integer $$$n$$$, a pair $$$(a,b)$$$ is considered cool only if:

  • $$$1 \le a \lt b \le n$$$;
  • $$$a$$$ $$$\&$$$ $$$b$$$ $$$=$$$ $$$0$$$, where $$$\&$$$ denotes the bitwise AND operation.

For a given integer $$$n$$$, find the maximum value of $$$\gcd(a,b)$$$ among all cool pairs $$$(a, b)$$$. Here $$$\gcd$$$ means the greatest common divisor.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of test cases.

For each test case, the only line contains a single integer $$$n$$$ $$$(2 \le n \le 10^9)$$$.

Output

For each test case, print the maximum value of $$$\gcd(a,b)$$$ for all cool pairs $$$(a, b)$$$.

Example
Input
9
2
3
4
5
6
7
8
9
10
Output
1
1
2
2
2
2
4
4
5

D. Tuples Fusion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ tuples $$$(a_i,b_i)$$$. In the beginning, your score is $$$0$$$.

You can do the following operation any number of times in any order:

  1. Choose an index $$$i$$$ ($$$1\le i\le n$$$), add $$$(a_i+b_i)^2$$$ to your score, then set $$$a_i=b_i=0$$$;
  2. Choose two distinct indexes $$$i,j$$$ ($$$1\le i,j\le n$$$), add $$$a_j^2$$$ to your score, add $$$b_j$$$ to $$$b_i$$$, then set $$$a_j=b_j=0$$$.
  3. Choose two distinct indexes $$$i,j$$$ ($$$1\le i,j\le n$$$), add $$$b_j^2$$$ to your score, add $$$a_j$$$ to $$$a_i$$$, then set $$$a_j=b_j=0$$$.
Find the maximum score you can get.
Input

The first line contains a single integer $$$t$$$ ($$$1 \le t\le 10^4$$$), the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n\le 2 \cdot 10^5$$$).

The next $$$n$$$ lines of each test case contain two integers $$$a_i,b_i$$$ ($$$1\le a_i,b_i\le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ for all tests does not exceed $$$2 \cdot 10^5$$$, and the answer for each test case won't exceed $$$9.2 \cdot 10^{18}$$$.

Output

For each test case, output the maximum score you can get.

Example
Input
3
2
1 1
1000000000 1000000000
3
1 3
2 6
3 9
6
85 65
35 59
2 65
789 21
12 32
9 8
Output
4000000004000000002
446
1220694
Note

In the first case, we can do the following operations:

  • Choose $$$i=2$$$ and $$$j=1$$$, add $$$b_j^2$$$ to your score, add $$$a_j$$$ to $$$a_i$$$, then set $$$a_i=b_i=0$$$. After that, $$$(a_1,b_1)=(0,0)$$$, $$$(a_2,b_2)=(1000000001,1000000000)$$$ and you score is $$$1$$$;
  • Choose $$$i=2$$$ add $$$(a_i+b_i)^2$$$ to your score, then set $$$a_i=b_i=0$$$. After that, $$$(a_1,b_1)=(0,0)$$$, $$$(a_2,b_2)=(0,0)$$$ and you score is $$$4000000004000000002$$$.

It can be proven that $$$4000000004000000002$$$ is the maximum of your score.

You can also do the following operations to get the maximum of your score:

  • Choose $$$i=2$$$ and $$$j=1$$$, add $$$a_j^2$$$ to your score, add $$$b_j$$$ to $$$b_i$$$, then set $$$a_i=b_i=0$$$. After that, $$$(a_1,b_1)=(0,0)$$$, $$$(a_2,b_2)=(1000000000,1000000001)$$$ and you score is $$$1$$$;
  • Choose $$$i=2$$$, add $$$(a_i+b_i)^2$$$ to your score, then set $$$a_i=b_i=0$$$. After that, $$$(a_1,b_1)=(0,0)$$$, $$$(a_2,b_2)=(0,0)$$$ and you score is $$$4000000004000000002$$$.

E. Fun is Counting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$.

An array $$$b$$$ of size $$$n$$$ is considered valid if and only if:

  • $$$1 \le b_i \le n$$$ for all $$$1 \le i \le n$$$;
  • If $$$b_i$$$ is removed from the array $$$b$$$, there are exactly $$$a_i$$$ different numbers in the array $$$b$$$.

Count the number of different multisets $$$\{b_1,b_2,\ldots,b_n\}$$$ composed of each valid array $$$b$$$ modulo $$$998244353$$$.

Note that the order of numbers is not important in a multiset. For example, $$$\{1,1,2\}$$$ and $$$\{2,1,1\}$$$ are considered the same, but $$$\{1,1,2\}$$$ and $$$\{2,1,2\}$$$ are not.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$1 \le a_{i} \le n-1$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output in a new line  — the number of different multisets $$$\{b_1,b_2,\ldots,b_n\}$$$ composed of each valid array $$$b$$$ modulo $$$998244353$$$.

Example
Input
6
2
1 1
3
2 2 2
3
2 1 2
4
1 2 3 2
4
3 3 2 2
6
3 3 2 2 3 3
Output
3
1
6
0
12
60
Note

In the first test case, there are four valid arrays  — $$$[1,1]$$$,$$$[2,2]$$$,$$$[1,2]$$$ and $$$[2,1]$$$. Thus, there are three different multisets $$$\{1,1\}$$$,$$$\{2,2\}$$$ and $$$\{1,2\}$$$.

In the second test case, there is only one multiset $$$\{1,2,3\}$$$.

F. Mad MAD Sum II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer array $$$a$$$ of length $$$n$$$, your task is to find the value of $$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])$$$.

The $$$\operatorname{MAD}$$$ in an array is the largest value that appears at least twice in the array. If every value appears exactly once in the array, then its $$$\operatorname{MAD}$$$ value is $$$0$$$.

For example, $$$\operatorname{MAD}([1, 2, 2, 5, 5]) = 5$$$ and $$$\operatorname{MAD}([1, 2, 5]) = 0$$$.

Input

The first line of the input contains exactly one integer, $$$t$$$ $$$(1 \le t \le 3 \cdot 10^4)$$$, the number of testcases.

The first line of each testcase contains exactly one integer, $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$, the length of the array.

The second line of each testcase contains exactly $$$n$$$ integers, $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^8)$$$.

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

Output

For each test case, output an integer in a new line — $$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])$$$.

Example
Input
3
2
1 2
4
4 2 2 4
8
5 2 1 2 1 5 2 1
Output
0
10
40
Note

In the first test case, $$$$$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])=\operatorname{MAD}([a_1,a_2])=\operatorname{MAD}([1,2])=0. $$$$$$

In the second test case, the following table summarizes the $$$\operatorname{MAD}$$$ of each subarray. $$$$$$ \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & & 0 & 2 & 4 \\ 2 & & & 2 & 2 \\ 3 & & & & 0 \\ 4 & & & & \end{array} $$$$$$ The sum of all $$$\operatorname{MAD}$$$ values is $$$10$$$.

G. Not An SQRT Problem
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree of size $$$n$$$ rooted at node $$$1$$$. At first, values of all nodes are equal to $$$0$$$.

Process $$$q$$$ queries of four types:

  • "1 x v": add $$$v$$$ to all nodes in the subtree rooted at node $$$x$$$;
  • "2 x v": add $$$v$$$ to all child nodes of node $$$x$$$. It is guaranteed that $$$x$$$ has at least one child node;
  • "3 x": query the maximum value in the subtree rooted at node $$$x$$$;
  • "4 x": query the maximum value among all child nodes of node $$$x$$$. It is guaranteed that $$$x$$$ has at least one child node;
Input

The first line contains two space-separated integers $$$n$$$ and $$$q$$$ $$$(2 \leq n,q \leq 3 \cdot 10^5)$$$, representing the number of nodes in the tree.

The following $$$n-1$$$ lines describe the edges of the tree. Each line contains two space-separated integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), indicating an edge between nodes $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the input data represents a tree.

The next $$$q$$$ lines describe the operations:

  • "1 x v": add $$$v$$$ ($$$-10^9 \le v \le 10^9$$$) to all nodes in the subtree rooted at node $$$x$$$ ($$$1 \le x \le n$$$);
  • "2 x v": add $$$v$$$ ($$$-10^9 \le v \le 10^9$$$) to all children of node $$$x$$$ ($$$1 \le x \le n$$$). It is guaranteed that $$$x$$$ has at least one child node;
  • "3 x": query the maximum value in the subtree rooted at node $$$x$$$ ($$$1 \le x \le n$$$);
  • "4 x": query the maximum value among all children of node $$$x(1 \le x \le n)$$$. It is guaranteed that $$$x$$$ has at least one child node.
Output

For each query of type $$$3$$$ or $$$4$$$, output the corresponding maximum value. Each result should be on a new line.

Example
Input
5 10
1 2
1 3
2 4
2 5
3 1
1 1 1
1 2 2
2 1 -5
3 2
4 1
3 1
2 2 -3
4 1
3 1
Output
0
3
-2
3
-2
1