Replay of BU - PSTU Programming club collaborative contest
A. Convolution XOR SUM
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$.

For a permutation $$$p_1, p_2, \ldots, p_n$$$ of $$$(1, 2, \ldots, n)$$$, let's define the score $$$S(p)$$$ of $$$p$$$ as follows.

  • $$${\displaystyle S(p) = \sum_{i = 1} ^{n} {a_{p_i}}\oplus b_i}$$$
where $$$\oplus$$$ denotes the bitwise XOR operation.

There are $$$n!$$$ permutations of $$$p$$$ of $$$(1, 2, \ldots, n)$$$. Find the sum, modulo $$$10^9+7$$$, of the scores of those permutations.

  • Formally, let $$$s_n$$$ be the set of the permutations of $$$(1, 2, \ldots, n)$$$. compute the following $$${\displaystyle \sum_{p \in s_n} {S(p)}} \bmod{10^9+7}$$$

A permutation is a sequence of $$$n$$$ integers from $$$1$$$ to $$$n$$$, in which all numbers occur exactly once. For example, $$$[1], [3,5,2,1,4], [1,3,2]$$$ are permutations, and $$$[2,3,2], [4,3,1], [0]$$$ are not.

Input

The first line of the input contains an integer $$$n$$$ $$$(1\le n \le 10^5)$$$ — the length of the array.

The second line of the input contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \le a_i \le 10^5)$$$ — the elements of the array $$$a$$$.

The third line of the input contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ $$$(1 \le b_i \le 10^5)$$$ — the elements of the array $$$b$$$.

Output

Print the sum of the scores, modulo $$$10^9+7$$$, for all permutations of length $$$n$$$.

Examples
Input
3
1 2 3
1 2 3
Output
24
Input
3
2 2 2
3 4 4
Output
78
Note

In the first case, all of the permutations of the array $$$a$$$ are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$ and the scores are $$$[0, 2, 6, 6, 6, 4]$$$. respectively. So, the result is $$$0+2+6+6+6+4=24$$$.

B. Convolution SUM XOR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$.

For a permutation $$$p_1, p_2, \ldots, p_n$$$ of $$$(1, 2, \ldots, n)$$$, let's define the score $$$S(p)$$$ of $$$p$$$ as follows.

  • $$${\displaystyle S(p) = \bigoplus_{i = 1} ^{n} {a_{p_i}}+ b_i}$$$ i.e. $$$S(p) = (a_{p_1}+ b_1) \oplus (a_{p_2}+ b_2) \ldots (a_{p_n}+ b_n)$$$
where $$$\oplus$$$ denotes the bitwise XOR operation.

There are $$$n!$$$ permutations of $$$p$$$ of $$$(1, 2, \ldots, n)$$$. Find the sum, modulo $$$10^9+7$$$, of the scores of those permutations.

  • Formally, let $$$s_n$$$ be the set of the permutations of $$$(1, 2, \ldots, n)$$$. compute the following $$${\displaystyle \sum_{p \in s_n} {S(p)}} \bmod{10^9+7}$$$

A permutation is a sequence of $$$n$$$ integers from $$$1$$$ to $$$n$$$, in which all numbers occur exactly once. For example, $$$[1], [3,5,2,1,4], [1,3,2]$$$ are permutations, and $$$[2,3,2], [4,3,1], [0]$$$ are not.

Input

The first line of the input contains an integer $$$n$$$ $$$(1\le n \le 16)$$$ — the length of the array.

The second line of the input contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \le a_i \le 10^8)$$$ — the elements of the array $$$a$$$.

The third line of the input contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ $$$(1 \le b_i \le 10^8)$$$ — the elements of the array $$$b$$$.

Output

Print the sum of the scores, modulo $$$10^9+7$$$, for all permutations of length $$$n$$$.

Examples
Input
3
1 2 3
1 2 3
Output
16
Input
3
2 2 2
3 4 4
Output
30
Note

In the first case, all of the permutations of the array $$$a$$$ are $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$ and the scores are $$$[0, 2, 6, 2, 2, 4]$$$ respectively. So, the result is $$$0+2+6+2+2+4=16$$$.

C. Play With Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters.

For each index $$$i$$$, calculate what is the maximum length of the palindromic substring which includes $$$i$$$-th index.

In other words, for each index $$$i$$$, find the maximum value of $$$r - l + 1$$$ where $$$s[l\ldots r]$$$ is a palindrome and $$$(1 \le l \le i \le r \le n)$$$

Suppose s = acab. Hence, for index $$$1$$$, $$$2$$$, and $$$3$$$ the answer is $$$3$$$ (acab, the underlined part is the maximum such palindromic substring), for the index, $$$4$$$ the answer is $$$1$$$ (acab, the underlined part is the maximum such palindromic substring).

A string $$$s[1\ldots n]$$$ of length $$$n$$$ is palindromic if $$$s[i]=s[n-i+1]$$$ for every $$$1 \le i \le n$$$.

The string $$$s[l\ldots r]$$$ is a substring of string $$$s[1\ldots n]$$$ for every $$$1 \le l \le r \le n$$$.

Input

The input data contains several test cases. The first line contains one integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The description of the test cases follows.

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

The second line for each test case contains a single string, $$$s$$$ of $$$n$$$ lowercase Latin letters.

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

Output

For each test case, output $$$n$$$ integers — $$$i$$$-th of which is the answer for index $$$i$$$.

Example
Input
2
10
astthemota
9
adaadaaxz
Output
1 1 2 2 1 1 1 1 1 1 
6 6 6 6 6 6 5 1 1
Note

For the 1st test, for index: $$$3$$$ and $$$4$$$ we can select palindrome substring tt (astthemota). But for other indexes, we can't select any palindromic substring of more than $$$1$$$ length, which includes that index also.

D. Median Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, a_2, \ldots, a_n$$$ consisting of $$$n$$$ integers.

Let's define $$$p$$$, $$$q$$$ and $$$x$$$ as follows:

  • $$$p$$$ is the minimum possible sum of a subsequence of $$$a$$$.
  • $$$q$$$ is the maximum possible sum of a subsequence of $$$a$$$.
  • $$$x$$$ is the sum of any arbitrary subsequence, $$$s$$$, of $$$a$$$.
Your target is to choose an arbitrary subsequence, $$$s$$$, of $$$a$$$ for which $$$|2\cdot x - (p + q)|$$$ is minimum possible.

Print the minimum possible value of $$$|2\cdot x - (p + q)|$$$.

Subsequence of an array can be obtained by erasing some (possibly zero or all) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array $$$[5,3,1,2,4]$$$ the following arrays are subsequences: $$$[3], [5,3,1,2,4], [5,1,4]$$$, but the array $$$[1,3]$$$ is not.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the length of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ $$$(-500 \le a_i \le 500)$$$ — elements of the array $$$a$$$.

Output

Print the minimum possible value of $$$|2\cdot x - (p + q)|$$$.

Examples
Input
3
3 -2 4
Output
1
Input
2
1 2
Output
1
Note

In the first case, $$$p=-2$$$ and $$$q=7$$$. Let $$$s = [-2, 4]$$$ then $$$x=-2+4=2$$$ and $$$|2\cdot x-(p+q)|=1$$$. And, this is the minimum possible answer.

E. A Random Traveller
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hey, I'm sure that you love to travel a lot. Now, you have $$$n$$$ cities left in your wish list, $$$i$$$-th of which costs $$$a_i$$$ to visit, and obviously, you want to visit all of them. To do so, you will follow the following steps:

  1. Choose a random city, numbered $$$i$$$ uniformly in the range from $$$1$$$ to $$$n$$$ and visit city $$$i$$$.
  2. In case you have successfully visited all cities, stop your journey.
  3. Otherwise, go to step $$$1$$$.

Note that, you may visit one city more than once. Find the expected total cost you need to visit all the $$$n$$$ cities. It can be shown that it can be represented as $$$\frac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers and $$$q \ne 0 \bmod{10^9+7}$$$. Print the value of $$$p \cdot q^{-1} \bmod{10^9+7}$$$.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of cities.

The following line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — $$$i$$$-th of which represents the costs of visiting city $$$i$$$ i.e. $$$a_i$$$ $$$(1 \le a_i \le 10^5)$$$.

Output

Print a single integer — the expected total cost to visit all the cities written as $$$p \cdot q^{-1} \bmod{10^9+7}$$$.

Examples
Input
3
1 2 3
Output
11
Input
1
5
Output
5

F. Oh no, Again Query?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. Initially, there is a single integer written on every vertex: the vertex $$$i$$$ has $$$p_i$$$ written on it.

You have to process $$$q$$$ queries of three types:

  • $$$1$$$ $$$i$$$ — delete the $$$i$$$-th edge from the graph.
  • $$$2$$$ $$$u$$$ $$$x$$$ — change the value of $$$p_u$$$ to x, i.e. $$$p_u := x$$$.
  • $$$3$$$ $$$v$$$ — among all vertices reachable from the vertex $$$v$$$ using the edges of the graph(including the vertex $$$v$$$ itself), find a vertex $$$u$$$ with the largest number $$$p_u$$$ written on it, print $$$p_u$$$.
Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^{5})$$$ — the number of vertices of the graph and the number of edges of the graph.

The second line contains $$$n$$$ space-separated integers $$$p_1, p_2, \ldots, p_n$$$ — $$$p_i$$$ is the number initially written on vertex $$$i(1 \le p_i \le 10^9)$$$.

Then $$$m$$$ lines follow, the $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le n, a_i \neq b_i)$$$ and means that the $$$i$$$-th edge connects vertices $$$a_i$$$ and $$$b_i$$$. It is guaranteed that the graph does not contain multi-edges.

The next line contains a single integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.

The $$$q$$$ lines follow, which describe the queries. Each line is given by one of the following formats:

  • $$$1$$$ $$$i$$$ — denotes a query of the first type with an edge $$$i$$$ $$$(1 \le i \le m)$$$. For each query of the first type, it is guaranteed that the corresponding edge is not deleted from the graph yet.
  • $$$2$$$ $$$u$$$ $$$x$$$ — denotes a query of the second type, with a vertex $$$u(1 \le u \le n)$$$ and a value $$$x(1 \le x \le 10^9)$$$.
  • $$$3$$$ $$$v$$$ — denotes a query of the third type, with a vertex $$$v(1 \le v \le n)$$$.
Output

For every query of the third type, print the value of $$$p_u$$$ written on the chosen vertex $$$u$$$.

Example
Input
7 6
4 7 3 4 3 2 1
1 2
1 5
2 4
2 5
3 6
3 7
6
3 1
1 1
1 2
3 1
2 7 10
3 3
Output
7
4
10
Note

In the 1st test, the initial graph is,

For the 1st query, vertex 1,2,4,5 are reachable from vertex-1 and the largest value is 7, written on vertex-2.

For the 2nd and 3rd queries, we delete the 1st, and 2nd edge. Then the updated graph is,

In the 4th query, the largest value is 4 found on vertex-1, which is the only node reachable from vertex-1.

In the 5th query, the updated value of vertex-6 is 10.

In the 6th query, the largest value is 10 found on vertex-6.

G. Minimum Enclosing Axis-Parallel Square
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ points on a plane. The coordinates of the $$$i$$$-th point are $$$(x_i, y_i)$$$.

Print the minimum possible area of a square whose sides are parallel to the $$$x$$$ and $$$y$$$ axis, and cover all of the points.

Input

The input data contains several test cases. The first line contains one integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The description of the test cases follows.

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

Then $$$n$$$ lines follow, each line containing two integers $$$x_i$$$ and $$$y_i$$$ $$$(|x_i|, |y_i| \le 10^9)$$$ — the coordinates of $$$i$$$-th point.

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

Output

For each test case, print a single integer — the minimum possible area of the square.

Example
Input
2
4
1 0
-1 0
0 1
0 -1
3
2 0
-2 0
0 2
Output
4
16

H. Maximum Product
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, you need to find $$${\displaystyle\max_{1 \le i \lt j \lt k \le n}{a_i\cdot a_j \cdot a_k}}$$$

Input

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

The first line of each test case contains an integer $$$n$$$ $$$(3\le n \le 10^5)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(|a_i| \le 10^6)$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test, print the answer in a single line.

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

I. Hail Pythagoras
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. You have to count the number of possible tuples $$$(a,b,c)$$$ such that $$$a \le b \le c$$$ and $$$a^2 + b^2 = c^2$$$ where $$$1 \le a \le n$$$.

Input

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

Each of the following $$$t$$$ lines contains one integer $$$n$$$ $$$(1 \le n \le 10^5)$$$.

Output

Print the number of possible tuples $$$(a,b,c)$$$ such that $$$a \le b \le c$$$ and $$$a^2 + b^2 = c^2$$$ where $$$1 \le a \le n$$$.

Example
Input
3
12
13
15
Output
11
12
16
Note

For test case 2, the expected tuples are listed below:

  • $$$(3, 4, 5)$$$
  • $$$(5, 12, 13)$$$
  • $$$(6, 8, 10)$$$
  • $$$(7, 24, 25)$$$
  • $$$(8, 15, 17)$$$
  • $$$(9, 12, 15)$$$
  • $$$(9, 40, 41)$$$
  • $$$(10, 24, 26)$$$
  • $$$(11, 60, 61)$$$
  • $$$(12, 16, 20)$$$
  • $$$(12, 35, 37)$$$
  • $$$(13, 84, 85)$$$

J. Giveaway?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Are you hear the name Team_Robust ? It's a programming contest team from Barisal University, Bangladesh.They have done an excellent job in any recent onsite contest.

But unfortunately, this team will not participate in any new onsite contests. Are you sad to hear that? Me also. 😢

Just print the best team name of Barisal University.

Output

Print the best team name of Barisal University.