PSUT Marathon 2025
A. Honeymoon Grand Prix (Red)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mario is optimizing the track layout for the next Honeymoon Grand Prix!

He's found a flat, rectangular section of the track measuring $$$x$$$ units long and $$$y$$$ units wide.

He wants to install the largest possible square boost pad entirely within this rectangular section to give racers an extra burst of speed. He is interested in the area of the pad.

Mario's Boost Pad.

Given the dimensions $$$x$$$ and $$$y$$$ of the rectangular section, what is the side length of the largest square boost pad Mario can install?

Input

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

Each of the next $$$t$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^3$$$) — the dimensions of the rectangular section of the track.

Output

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

Example
Input
3
1 1
5 3
7 7
Output
1
9
49

B. Baran Circuit (Blue)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Baran is Mario's new friend, and Baran friends are racing on a new track that's shaped like a tree with $$$n$$$ nodes rooted at $$$1$$$. Each node $$$i$$$ on the track has a "Coin Value" of $$$a_i$$$.

Baran new logo.

To calculate the total score for the race, they need to consider every possible pair of nodes $$$(i, j)$$$ on the track (including pairs where $$$i=j$$$).

For each pair, they find the Lowest Common Ancestor (LCA) of $$$i$$$ and $$$j$$$, let's call it $$$l = \text{lca}(i, j)$$$.

The score contributed by the pair $$$(i, j)$$$ is $$$\gcd(a_i, a_j, a_l)$$$.

Your task is to find the sum of these scores for all possible pairs of nodes $$$(i, j)$$$ $$$(i \le j)$$$.

Formally, calculate

$$$$$$\sum_{i=1}^n \sum_{j=i}^n \gcd(a_i, a_j, a_{\text{lca}(i, j)})$$$$$$

Input

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the Coin Values for each node.

The next $$$n-1$$$ lines describe the tree edges. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — representing an edge between nodes $$$u$$$ and $$$v$$$.

Output

Output a single integer, the total sum of $$$\gcd(a_i, a_j, a_{\text{lca}(i, j)})$$$ over all pairs $$$1 \le i, j \le n$$$.

Example
Input
4
4 2 1 4
1 2
1 3
1 4
Output
22

C. Queen Bee Last Stand Off (Brown)
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

High above the track, contestants face off on a massive $$$n \times m$$$ grid.

The Queen likes Yellow and Black because they are her colors.

Queen Bee.

The grid is initially filled with ('.'). Then, a sequence of moves is played, with each move consisting of painting a cell either Black ('B') or Yellow ('Y'). Each day, two bees compete against each other in a tough match on the grid, where one bee paints cells Yellow and the other paints cells Black.

The game is simple: they fight 1v1, and the winner earns the right to choose any empty cell and paint it with his color.

The tension is great—the first bee to achieve a line of at least $$$k$$$ connected pieces of their color, horizontally, vertically, or diagonally, will not only earn Queen Bee's respect but also the legendary Queen Honey Pot as a prize and victory!

However, due to the intensity of the competition, they forgot about the $$$k$$$-connected-pieces rule, and eventually, they ended up coloring the entire grid (they played exactly $$$n \times m$$$ moves).

Now, they want to iterate through the moves again to determine the actual winner.

Given $$$n$$$, $$$m$$$, $$$k$$$, and the sequence of moves, determine which bee achieves a line of length at least $$$k$$$ first. If neither achieves this, the game results in a draw.

Input

The first line contains three space integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 1000$$$, $$$1 \le k \le \min(n, m)$$$) — denotes the number of rows, is the number of columns, and the number of connected cells of the same color (Black or Yellow) required, respectively.

The next $$$n \cdot m$$$ lines represent the sequence of moves, the $$$i_{th}$$$ line contains three integers $$$p \in$$$ ('B', 'Y') which represents the color of bee that won the $$$i_{th}$$$ move, $$$x$$$ ($$$1 \le x \le n$$$), and $$$y$$$ ($$$1 \le y \le m$$$) — $$$x$$$, $$$y$$$ are the coordinates of the cell respectively.

Output

Print one of the following characters:

  • B if Black has a winning connection of length $$$k$$$.
  • Y if Yellow has a winning connection of length $$$k$$$.
  • N if neither Black nor Yellow has a winning connection of length $$$k$$$ in the given state.
Example
Input
3 3 3
B 1 1
Y 2 1
B 1 2
Y 2 2
B 1 3
Y 3 1
Y 3 2
Y 3 3
Y 2 3
Output
B

D. Chaos vs Stability Factor (Pink)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mario and Luigi are analyzing segments of the ultimate Mario Kart Grand Prix course.

The course is incredibly long, consisting of sections indexed by positive integers starting from 1.

Mario flying around.

For a continuous segment of the course from index $$$l$$$ to index $$$r$$$ (inclusive), they calculate two special values based on the section indices:

  1. Chaos Factor: The bitwise XOR of all section indices from $$$l$$$ to $$$r$$$ ($$$l \oplus (l+1) \oplus \dots \oplus r$$$).
  2. Stability Factor: The bitwise AND of all section indices from $$$l$$$ to $$$r$$$ ($$$l \ \& \ (l+1) \ \& \ \dots \ \& \ r$$$).

Given several queries, each specifying a range $$$[l, r]$$$, determine if the Chaos Factor for that range is greater than or equal to the Stability Factor.

Input

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

Each of the following $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$).

Output

For each query, output "YES" if the Chaos Factor is $$$\ge$$$ the Stability Factor, and "NO" otherwise. (case insensitive)

Example
Input
3
1 1
1 2
2 3
Output
Yes
Yes
No

E. Strawberry Mushroom Cells (Yellow)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an $$$N \times N$$$ grid representing a section of a Mario Kart track. Each cell contains a non-negative integer.

  • A cell with value 0 denotes a racer.
  • A cell with a positive value denotes a strawberry mushroom item block containing that many strawberry mushrooms.

Each racer is positioned at a fixed cell (with value 0) and cannot move to any other location. From this position, they can instantly collect all strawberry mushrooms from their immediately adjacent cells (up, down, left, and right). Each racer collects mushrooms independently, so the same mushroom block can be fully collected by multiple racers if it is adjacent to more than one of them.

Red Mushroom fan club

Find a single racer who can collect the maximum total number of strawberry mushrooms from their adjacent cells. Output their 0-indexed row and column.

If multiple racers can collect the same maximum amount, output the one with the lowest coordinates. Coordinates $$$(r_1, c_1)$$$ are considered lower than $$$(r_2, c_2)$$$ if $$$r_1 \lt r_2$$$, or if $$$r_1 = r_2$$$ and $$$c_1 \lt c_2$$$.

Note: It is guaranteed that the grid has at least one racer in it.

Input

The first line contains a single integer $$$N$$$ ($$$2 \le N \le 1000$$$) — the size of the grid.

Then $$$N$$$ lines follow, each with $$$N$$$ non-negative $$$a_{i,j}$$$ ($$$0 \le a_{i,j} \le 10^6$$$) — the number written in each cell.

Output

Output two space-separated integers: the row and column of a racer who can collect the most mushrooms (0-indexed).

If multiple racers can collect the same maximum amount, output the one with the lowest coordinates. Coordinates $$$(r_1, c_1)$$$ are considered lower than $$$(r_2, c_2)$$$ if $$$r_1 \lt r_2$$$, or if $$$r_1 = r_2$$$ and $$$c_1 \lt c_2$$$.

Examples
Input
3
0 2 0
1 0 3
0 4 0
Output
1 1
Input
3
10 0 10
5 5 5
10 0 12
Output
2 1

F. Mario and Peach MEX Therapy (Orange)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Moon had the worst breakup ever, again. His ex was way smarter than him, which devastated him.

So, he needed advice from the one and only Apple, again. Apple decided to take Moon to Couple Therapy since he has been in too much relationships issues.

Moon said, "4 JAYYED."

Apple introduced Moon to Mario and Peach, and as Moon began to open up, Mario and Peach decided to help Moon.

Mario and Peach discussing how to help Moon.

They gave Moon an array of $$$n$$$ non-negative integers, Moon has to find the minimum $$$\operatorname{MEX}$$$ (Minimum EXcluded value) among all its non-empty sub-arrays, and count how many non-empty sub-arrays achieve this minimum $$$\operatorname{MEX}$$$.

Can you help Moon solve this problem?

Note: The $$$\operatorname{MEX}$$$ (Minimum EXcluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The $$$\operatorname{MEX}$$$ of $$$[1, 2, 3]$$$ is $$$0$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 2]$$$ is $$$3$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 3]$$$ is $$$2$$$
Input

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

For each test case:

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

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

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

Output

For each test case, output the count how many non-empty sub-arrays achieve the minimum $$$\operatorname{MEX}$$$

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

An array $$$b$$$ is a sub-array of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

In particular, an array is a sub-array of itself.

G. Mario's Cheesy Tuna Pit Stop (Grey)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

During a brief break from racing, Mario is making $$$n$$$ delicious tuna sandwiches.

Each sandwich requires exactly two slices of cheese. There are two types of cheese available: Mushroom Cheese and Star Cheese.

Mario follows a specific, repeating pattern for the cheese slices in his sandwiches:

  • The first sandwich uses two slices of Mushroom Cheese (Mushroom Cheese, Mushroom Cheese).
  • The second sandwich uses one slice of Mushroom Cheese and one slice of Star Cheese (Mushroom Cheese, Star Cheese).
  • The third sandwich uses two slices of Star Cheese (Star Cheese, Star Cheese).
This pattern repeats for all subsequent sandwiches (the 4th sandwich is like the 1st, the 5th like the 2nd, and so on).
Mario Kart Sandwich.

Mario wants to make $$$n$$$ sandwiches, determine the total number of Mushroom Cheese slices and the total number of Star Cheese slices he will need.

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 contain a single integer $$$n$$$ ($$$3 \le n \le 10^9$$$) — representing the total number of sandwiches.

Output

Output $$$t$$$ lines each line contain two space-separated integers: the total number of Mushroom Cheese slices followed by the total number of Star Cheese slices required.

Example
Input
2
3
8
Output
3 3
9 7

H. Good Luck Counting Mario ! (Purple)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the Mario Elite League!

You're preparing your kart for the upcoming races, the kart has $$$n$$$ item slots.

Mario Elite League

Each slot $$$i$$$ must be filled with an item of "Power Level" $$$A_i$$$.

To achieve peak performance, the array of Power Levels $$$[A_1, A_2, \dots, A_n]$$$ must satisfy the following conditions based on their combined effects:

  1. The Greatest Common Divisor (GCD) of all Power Levels must be exactly $$$g$$$. $$$$$$ \gcd(A_1, A_2, \dots, A_n) = g $$$$$$
  2. The Least Common Multiple (LCM) of all Power Levels must be exactly $$$l$$$. $$$$$$ \operatorname{lcm}(A_1, A_2, \dots, A_n) = l $$$$$$

Given integers $$$n, g, l$$$, Mario wants to count the number of distinct arrays $$$[A_1, A_2, \dots, A_n]$$$ satisfying these conditions.

Since the number of such arrays can be very large, output the answer modulo $$$10^9 + 7$$$.

Input

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

The only line in each test case contains four space-separated integers $$$n$$$ ($$$1 \le n \le 10^6$$$), $$$g, l$$$ ($$$1 \le g, l \le 10^{12}$$$) — the number of items, the gcd, and the lcm respectively.

It's guaranteed that the sum of $$$g, l$$$ over all test cases does not exceed $$$1 \cdot 10^{12}$$$.

Output

For each test case, Print a single integer, the number of valid arrays modulo $$$10^9 + 7$$$.

Example
Input
3
2 2 6
3 1 4
6 6 24
Output
2
12
602

I. Leah's Grand Team Formation (Black)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In preparation for the next Grand Prix, racers are forming teams.

Each racer has a rating. Leah, the one managing the race has one rule for team formation:

If a racer's rating is greater than or equal to 1500, they compete in the Grand Prix solo. Otherwise, they must form teams of up to 3 members.

Teams

Given the rating scores of all racers, determine the minimum total number of teams required for the Grand Prix.

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 number of racers.

The second line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$100 \le r_i \le 3500$$$) — where $$$r_i$$$ is the rating score of the $$$i$$$-th racer.

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

Output

Output $$$t$$$ integer representing the minimum total number of teams for each test case.

Example
Input
3
4
1339 1664 1414 1632
3
1000 1000 1000
5
1600 1400 1200 1700 1500
Output
3
1
4

J. Mario Kart Bitwise Bash (Green)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As you race along the track, represented by an array $$$a$$$ of $$$n$$$ integers, each element $$$a[i]$$$ signifies a power-up available at position $$$i$$$. These power-ups have special bitwise properties.

For each possible range size $$$k$$$, from $$$1$$$ to $$$n$$$, a temporary array $$$b$$$ is created to evaluate the potential of power-ups.

Mario Bashing.

For each position $$$i$$$ on the track (from $$$1$$$ to $$$n$$$), the power-up at $$$b[i]$$$ is the bitwise OR of all power-ups $$$a[j]$$$ such that the absolute difference between your current position $$$i$$$ and the power-up's position $$$j$$$ is less than $$$k$$$.

Formally, for a given $$$k$$$: $$$$$$b[i] = \text{OR}_{1 \le j \le n, |i - j| \lt k} (a[j])$$$$$$

Your goal is to determine, for each value of $$$k$$$ from 1 to $$$n$$$, the bitwise AND of all elements in the array $$$b$$$.

Input

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_{n}$$$ ($$$0 \le a_i \lt 2^{30}$$$) — representing the power-ups at each position.

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

Output

Output $$$n$$$ integers, where the $$$k$$$-th integer is the bitwise AND of array $$$b$$$ for each $$$k$$$.

Example
Input
2
3
6 1 3
4
10 5 12 8
Output
0 3 7 
0 12 13 15

K. Mario and the Beautiful Blocks (White)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mario is embarking on a new adventure through the Mushroom Kingdom, and this time he's exploring a level made of $$$n$$$ blocks lined up in a row. Each block $$$i$$$ has a specific height $$$a_i$$$. The blocks are indexed from $$$1$$$ to $$$n$$$.

block.

For any continuous sequence of blocks, known as a sub-array, from index $$$l$$$ to $$$r$$$ (where $$$1 \le l \le r \le n$$$), its "beauty" is defined as the sum of height differences between adjacent blocks within that sub-array. Specifically, if $$$l \lt r$$$, the beauty is $$$(a_{l+1} - a_l) + (a_{l+2} - a_{l+1}) + \dots + (a_r - a_{r-1})$$$. If $$$l = r$$$ (a subarray with a single block), the beauty is $$$0$$$.

More formally, the beauty function for $$$l \lt r$$$ , $$$F(l,r)$$$ can be written as: $$$$$$ \sum_{i=l}^{r-1} (a_{i+1} - a_i) $$$$$$

The definition of beauty for the whole array is: $$$$$$ \sum_{l=1}^{n-1} \sum_{r=l+1}^{n} F(l,r) $$$$$$

Your goal is to find the beauty for the whole array.

Input

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

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

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_i \le 10^9$$$) — representing the heights of the blocks.

It's 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 representing the total sum of the beauty of all contiguous sub-arrays.

Example
Input
2
2
1 2
3
6 5 10
Output
1
8