Upper Egypt Programming Contest 2026 (UEPC 2026)
A. BedWars Replay
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After another long BedWars session, Muzan and Honey decided to create a highlights video from their match.

They have $$$N$$$ recorded clips, each represented by a string of lowercase English letters.

First, Honey must arrange the clips in any order, using every clip exactly once, and concatenate them into one long replay $$$T$$$.

Before uploading it, Muzan suggests starting the replay from a different moment. For an integer $$$k$$$ with $$$0 \le k \lt |T|$$$, a cyclic shift by $$$k$$$ characters moves the first $$$k$$$ characters of $$$T$$$ to the end. They may choose any such $$$k$$$ to obtain a new replay $$$T'$$$.

For example, if $$$T = \texttt{abcde}$$$, its possible cyclic shifts are:

abcde bcdea cdeab deabc eabcd

They are looking for a famous BedWars combo, represented by the string $$$P$$$.

Choose both the order of the clips and the cyclic shift so that the number of linear occurrences of $$$P$$$ as a substring of $$$T'$$$ is maximized. Occurrences are allowed to overlap.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 12$$$), the number of clips.

Each of the next $$$N$$$ lines contains a nonempty string $$$S_i$$$ ($$$1 \le |S_i| \le 50$$$).

The last line contains a nonempty string $$$P$$$ ($$$1 \le |P| \le 50$$$).

All strings contain only lowercase English letters.

Output

Print one integer, the maximum possible number of occurrences of $$$P$$$ after choosing the order of the clips and the cyclic shift.

Example
Input
2
baa
b
abba
Output
1
Note

The clips are $$$\texttt{baa}$$$ and $$$\texttt{b}$$$. The two possible concatenations are $$$\texttt{baab}$$$ and $$$\texttt{bbaa}$$$, and neither contains $$$\texttt{abba}$$$.

Rotating $$$\texttt{baab}$$$ by two characters gives $$$\texttt{abba}$$$, which contains the target exactly once. Therefore, the answer is $$$1$$$.

B. WisdomCasual's Deadline
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$\text{WisdomCasual}$$$ was supposed to prepare this problem for the $$$\text{UEPC}$$$ a week ago. Naturally, he forgot.

With only 30 minutes left before $$$\text{cgmoreda}$$$'s deadline, he scribbled down an idea involving arrays and operations. He thinks it is brilliant, but he has no time to solve it or assess its difficulty. He needs you to solve it for him and tell him the difficulty.

Here is the problem he wrote down:

You are given three integers $$$n$$$, $$$k$$$, and $$$x$$$. You need to construct an array $$$a$$$ of $$$n$$$ integers that satisfies the following conditions:

  1. $$$-k \le a_i \le k$$$ for all $$$1 \le i \le n$$$.
  2. The sum of all elements in the array is exactly $$$0$$$: $$$\sum_{i=1}^{n} a_i = 0$$$.
  3. The cost of the array is at most $$$x$$$.

The cost of an array is defined as the minimum number of operations required to make all elements in the array equal to $$$0$$$.

In one operation, you can choose an index $$$i$$$ ($$$1 \le i \lt n$$$) and do exactly one of the following:

  • Decrease $$$a_i$$$ by $$$1$$$ and increase $$$a_{i+1}$$$ by $$$1$$$.
  • Increase $$$a_i$$$ by $$$1$$$ and decrease $$$a_{i+1}$$$ by $$$1$$$.

Since $$$\text{WisdomCasual}$$$ wants to ensure the problem has a unique output, you must find the lexicographically smallest array $$$a$$$ that satisfies all the above conditions. (He doesn't have enough time to write a custom checker)

Can you solve it for him and save his deadline?

Note: An array $$$a$$$ is lexicographically smaller than an array $$$b$$$ of the same length if, at the first index where they differ, the element in $$$a$$$ is strictly smaller than the corresponding element in $$$b$$$.

Input

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

The only line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le 10^9$$$, $$$0 \le x \le 10^{18}$$$).

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 representing the lexicographically smallest valid array $$$a$$$.

It is guaranteed that under the given constraints, at least one valid array always exists.

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

C. Mixed Bits
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 $$$n$$$ integers. Only the lowest $$$m$$$ bits of every integer are considered.

Let $$$a_l, a_{l+1}, \ldots, a_r$$$ be a non-empty subarray. A bit position $$$b$$$ ($$$0 \le b \lt m$$$) is called mixed in this subarray if there is at least one element whose $$$b$$$-th bit is $$$0$$$, and at least one element whose $$$b$$$-th bit is $$$1$$$.

The value of a subarray is the number of its mixed bit positions.

Count the subarrays whose value is exactly $$$k$$$.

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 three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 20$$$, $$$0 \le k \le m$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt 2^m$$$).

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 one integer — the number of subarrays whose value is exactly $$$k$$$.

Example
Input
5
3 3 1
0 1 3
4 2 0
1 1 3 3
3 3 2
0 1 3
4 3 3
0 7 0 7
5 4 1
5 5 7 7 5
Output
2
6
1
6
8
Note

In the first test case, the array is $$$[0,1,3]$$$. In binary, its elements are $$$000$$$, $$$001$$$, and $$$011$$$.

The subarrays $$$[0,1]$$$ and $$$[1,3]$$$ have exactly one mixed bit. No other subarray does.

In the fourth test case, every subarray of length at least two has all three bits mixed.

D. The One and Only
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After Reda lost his gf, he told Baskot about it.

"Don't worry," Baskot said. "I'll find you a new gf."

Unfortunately, Baskot meant a generating function.

Find the polynomial with non-negative integer coefficients

$$$$$$ G(x) = c_0 + c_1x + c_2x^2 + \ldots + c_dx^d, $$$$$$

where $$$c_i \geq 0$$$ for every $$$i$$$ and $$$c_d \gt 0$$$, such that

$$$$$$ G(1) = a $$$$$$

and

$$$$$$ G(a+1) = b. $$$$$$

For arbitrary values of $$$a$$$ and $$$b$$$, such a polynomial may not exist. However, Baskot would never let his friend down, so he guarantees that exactly one valid polynomial exists for the given input.

Help Baskot introduce Reda to his new gf.

Yes, generating functions are usually infinite. This one has commitment issues. I mean, she is going to spend her time with Reda, after all.

Input

Two integers $$$a$$$ and $$$b$$$ ($$$1 \le a \le 10^6$$$, $$$1 \le b \le 10^{18}$$$) — the napkin, $$$G(1) = a$$$ and $$$G(a+1) = b$$$. It is guaranteed that exactly one such $$$G$$$ exists.

Output

On the first line, print $$$d+1$$$, the number of coefficients (with $$$c_d \gt 0$$$). On the second line, print $$$c_0, c_1, \dots, c_d$$$.

Examples
Input
3 9
Output
2
1 2
Input
7 322
Output
3
2 0 5
Note

In the first sample, $$$G(x) = 1 + 2x$$$, so $$$G(1) = 3$$$ and $$$G(4) = 9$$$.

In the second sample, $$$G(x) = 2 + 5x^2$$$, so $$$G(1) = 7$$$ and $$$G(8) = 322$$$.

E. Neighbor Reports
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Trida placed $$$n$$$ cards in a circle. The cards contain every integer from $$$1$$$ to $$$n$$$ exactly once, but their order is hidden.

For each position $$$i$$$, the judging team reports how many of the two neighboring cards contain a value smaller than the card at position $$$i$$$. Positions $$$1$$$ and $$$n$$$ are neighbors.

Given all reports, determine whether at least one circular ordering of the cards could produce them.

Input

The first line contains one integer $$$n$$$ ($$$3 \le n \le 2 \times 10^5$$$).

The second line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le 2$$$), where $$$r_i$$$ is the report for position $$$i$$$.

Output

Print YES if the reports can be produced by a permutation of $$$1,2,\ldots,n$$$ around the circle. Otherwise, print NO.

Examples
Input
3
0 1 2
Output
YES
Input
3
1 1 1
Output
NO
Note

In the first example, the circular values $$$1,2,3$$$ produce reports $$$0,1,2$$$.

F. Lighthouse
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A lighthouse stands vertically at sea level.

An observer is standing on a ship at an unknown eye height above sea level.

The total height of the lighthouse is $$$H$$$ meters.

The angle of depression from the observer to the base of the lighthouse is $$$\alpha$$$ degrees, and the angle of elevation from the observer to the top of the lighthouse is $$$\beta$$$ degrees.

This figure illustrates the first sample. Here, $$$H = 60$$$, $$$\alpha = 30^\circ$$$ is the angle of depression, and $$$\beta = 60^\circ$$$ is the angle of elevation.

For each test case, determine the observer's eye height above sea level.

Input

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

Each of the next $$$t$$$ lines contains three integers $$$\alpha, \beta, H$$$ where:

  • $$$1 \le \alpha \le 89$$$ — the angle of depression, measured in degrees.
  • $$$1 \le \beta \le 89$$$ — the angle of elevation, measured in degrees.
  • $$$1 \le H \le 10^6$$$ — the total height of the lighthouse, measured in meters.

It is guaranteed that all test cases are valid.

Output

For each test case, print the observer's eye height above sea level.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Example
Input
3
30 60 60
45 45 20
45 45 40
Output
15.0000000000
10.0000000000
20.0000000000
Note

The angle of depression is measured from the horizontal line passing through the observer's eye level down to the line of sight toward the base of the lighthouse, while the angle of elevation is measured from the horizontal line passing through the observer's eye level up to the line of sight toward the top of the lighthouse.

G. Sliding Reservations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A hall has $$$n$$$ seats numbered from $$$1$$$ to $$$n$$$. Team A has reserved three distinct seats $$$a_1,a_2,a_3$$$. Team B has written three distinct seat numbers $$$b_1,b_2,b_3$$$ on one reservation card.

Before submitting the card, Team B may choose any integer $$$k$$$ and add $$$k$$$ to all three numbers. Negative values of $$$k$$$ and $$$k=0$$$ are allowed.

Count the values of $$$k$$$ for which all three shifted numbers are between $$$1$$$ and $$$n$$$, and no shifted Team B reservation equals a Team A reservation.

Input

The first line contains one integer $$$n$$$ ($$$3 \le n \le 10^{18}$$$), the number of seats.

The second line contains three distinct integers $$$a_1,a_2,a_3$$$ ($$$1 \le a_i \le n$$$), the seats reserved by Team A.

The third line contains three distinct integers $$$b_1,b_2,b_3$$$ ($$$1 \le b_i \le n$$$), the numbers initially written by Team B.

Output

Print the number of valid integer values of $$$k$$$.

Example
Input
10
2 5 9
1 4 7
Output
2
Note

In the sample, keeping the card unchanged gives $$$k=0$$$, and shifting it three seats to the right gives $$$k=3$$$. The shifts $$$k=1$$$ and $$$k=2$$$ create collisions, while every other shift puts at least one reservation outside the hall.

H. History Lesson
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Input

The input contains the string Saad-Zaghloul.

Output

Print the year of the 1919 Egyptian Revolution.

Example
Input
Saad-Zaghloul
Output
1919

I. Closer or Equal
time limit per test
4 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices. The score of every vertex is initially $$$0$$$.

You have to process $$$q$$$ queries. Each query contains five integers $$$u$$$, $$$v$$$, $$$x$$$, $$$y$$$, and $$$z$$$. For every vertex $$$r$$$:

  • add $$$x$$$ to its score if $$$\operatorname{dist}(r,u) \lt \operatorname{dist}(r,v)$$$;
  • add $$$y$$$ to its score if $$$\operatorname{dist}(r,u) \gt \operatorname{dist}(r,v)$$$;
  • add $$$z$$$ to its score if $$$\operatorname{dist}(r,u) = \operatorname{dist}(r,v)$$$.

Here, $$$\operatorname{dist}(a,b)$$$ is the number of edges on the simple path between vertices $$$a$$$ and $$$b$$$.

After every query, print the minimum score among all vertices and the number of vertices having this score.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2\cdot 10^5$$$) — the number of vertices and the number of queries.

Each of the next $$$n-1$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a,b \le n$$$, $$$a \ne b$$$), denoting an edge between vertices $$$a$$$ and $$$b$$$. The given edges form a tree.

Each of the next $$$q$$$ lines contains five integers $$$u$$$, $$$v$$$, $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le u,v \le n$$$, $$$0 \le x,y,z \le 10^9$$$), describing a query.

Output

After every query, print two integers: the minimum score among all vertices and the number of vertices having this score.

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

After the first query, the scores of vertices $$$1,2,3,4$$$ are $$$1,4,4,1$$$, respectively. Thus, the minimum score is $$$1$$$, and two vertices have it.

In the last query, $$$u=v=3$$$, so every vertex is equally far from $$$u$$$ and $$$v$$$. Therefore, $$$z=2$$$ is added to every score.

J. Odd Minimum Subarrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers.

A non-empty subarray is a contiguous segment $$$a_l,a_{l+1},\ldots,a_r$$$ for some $$$1 \le l \le r \le n$$$. It is called good if its minimum element occurs an odd number of times within it.

Find the number of good subarrays of $$$a$$$.

Input

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

Each test case consists of two lines.

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

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).

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 one integer — the number of good subarrays.

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

K. One More One
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary grid $$$a$$$ with $$$n$$$ rows and $$$m$$$ columns.

Three cells form an angle if they can be written as $$$(i,j)$$$, $$$(i,y)$$$, and $$$(x,j)$$$, where $$$x \ne i$$$ and $$$y \ne j$$$, and all three cells contain $$$1$$$. The cell $$$(i,j)$$$ is the corner of the angle.

You must choose exactly one cell containing $$$0$$$ and change it to $$$1$$$.

Find the maximum possible number of angles after the change, and the number of cells whose change gives this maximum.

It is guaranteed that the grid contains at least one $$$0$$$.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) — the number of rows and columns.

Each of the next $$$n$$$ lines contains a binary string of length $$$m$$$ describing one row of the grid.

Each test case contains at least one $$$0$$$.

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

Output

For each test case, print two integers: the maximum possible number of angles and the number of cells whose change gives this maximum.

Example
Input
5
2 2
10
01
2 2
11
10
3 3
110
100
000
2 3
111
000
1 4
1010
Output
1 2
4 1
4 1
2 3
0 2
Note

In the first test case, either zero creates one angle. In the second, changing the only zero makes each of the four cells the corner of an angle. In the fourth, any cell in the second row creates two angles. In the fifth, a one-row grid cannot contain an angle, so either zero is optimal.

L. One Tangled Cable
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Trida attached $$$n$$$ cables to $$$2n$$$ sockets arranged from left to right. Every cable has a label from $$$1$$$ to $$$n$$$, and its two ends are attached to the two sockets carrying its label.

Two cables are tangled when their ends alternate along the row. In other words, cables $$$x$$$ and $$$y$$$ are tangled if the four relevant labels appear in the order $$$x,y,x,y$$$ or $$$y,x,y,x$$$, with other labels possibly between them.

Trida will remove exactly one entire cable, including both of its ends. Find all cables she can remove so that no two remaining cables are tangled. If zero or one cable remains after the removal, there is no tangled pair.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$), the number of cables.

The second line contains $$$2n$$$ integers $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \le a_i \le n$$$). Every integer from $$$1$$$ to $$$n$$$ occurs exactly twice.

Output

On the first line, print the number $$$k$$$ of cables whose removal leaves no tangled pair.

On the second line, print their $$$k$$$ labels in increasing order. If $$$k=0$$$, print an empty second line.

Example
Input
4
1 2 1 3 2 4 4 3
Output
1
2
Note

In the sample, removing cable $$$2$$$ leaves the sequence $$$1,1,3,4,4,3$$$, which has no tangled pair. Removing any other cable leaves at least one tangled pair.

M. Synchronized Arrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It is 5 AM, and $$$WisdomCasual$$$ is exhausted. He has been setting problems all night, and all he wants to do right now is get into bed and sleep. However, the problemset is still missing a problem.

In a desperate attempt to finish the problem and finally get some rest, he quickly writes down two arrays, $$$a$$$ and $$$b$$$, both of size $$$n$$$, and writes a random condition on a napkin.

He defines a pair of indices $$$(i, j)$$$ as synchronized if it satisfies the following conditions:

  1. $$$1 \le i \lt j \le n$$$
  2. The absolute difference between the elements in array $$$a$$$ is exactly equal to the absolute difference between the corresponding elements in array $$$b$$$. Formally: $$$\vert{}a_i - a_j\vert{} = \vert{}b_i - b_j\vert{}$$$

Since $$$WisdomCasual$$$ is already half-asleep, he leaves the task of actually counting the pairs to you. Help him find the total number of synchronized pairs so he can finally close his eyes and go to sleep...

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$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)  — the length of the arrays.

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

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

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 a single integer — the total number of synchronized pairs.

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

N. Two-Sided RPS
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The judging team lines up $$$n$$$ contestants, each showing Rock (R), Paper (P), or Scissors (S). Choose a divider between two adjacent contestants.

On the left, the leftmost contestant starts as champion and duels the others one by one from left to right toward the divider. On the right, the rightmost contestant starts as champion and duels the others one by one from right to left toward the divider. The two group champions then duel.

Rock beats Scissors, Scissors beats Paper, and Paper beats Rock. Equal gestures keep that same gesture as champion. Count the dividers for which the final champion shows the requested gesture.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \times 10^5$$$).

The second line contains a string $$$s$$$ of length $$$n$$$ over R, P, and S, in line order.

The third line contains one character $$$t$$$ (R, P, or S) — the requested gesture.

Output

Print the number of valid divider positions.

Example
Input
3
RPS
R
Output
1
Note

For the divider after the first contestant, the right group is won by Scissors, then Rock wins the final duel. For the other divider, Scissors wins the final duel. Therefore exactly one divider produces Rock.