SanSi Cup 2025
A. Google Search (Easy)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. In this version, $$$n, q \le 10^3$$$.

After years of competitive programming, Pacha is officially tired. Too many WAs, too many TLs, too many "elegant" data structures that only work in editorials. So he decided to do something different: build his own web search engine.

In a real search engine, searches are usually stored in a huge trie that grows with every new query. Pacha thought about doing it that way, and then remembered he had already suffered enough. To avoid dying with tries, he decided to reduce the problem to a simpler structure.

His search engine is modeled as a fixed tree with $$$n$$$ nodes. Each node represents a search category and stores a counter of how many times it has been searched. Initially, all counters are $$$0$$$.

The tree never changes shape or grows. The only thing that happens over time is that searches accumulate.

During $$$q$$$ days, events of two types are recorded:

  • Type $$$1$$$: a category receives new searches and its counter increases.
  • Type $$$2$$$: Pacha wants to know the $$$5$$$ most searched categories, in non-increasing order, within a part of his search engine represented by a subtree.

The tree is rooted at node $$$1$$$. The subtree of a node $$$v$$$ includes $$$v$$$ itself and all of its descendants.

Your task is to process all events and correctly answer every query.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^3$$$), the number of nodes of the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$), meaning there is an edge between $$$a_i$$$ and $$$b_i$$$. It is guaranteed that the edges form a tree.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^3$$$), the number of recorded events.

Each of the next $$$q$$$ lines describes an event. There are two possible types of events:

  • 1 $$$v$$$ $$$x$$$ — increase the counter of node $$$v$$$ by $$$x$$$ ($$$1 \le v \le n$$$, $$$1 \le x \le 10^3$$$).
  • 2 $$$v$$$ — query: report the $$$5$$$ largest values, in non-increasing order, within the subtree of $$$v$$$ ($$$1 \le v \le n$$$).
Output

For each query of type $$$2$$$, print a line with exactly $$$5$$$ integers in non-increasing order.

Note: if the subtree of node $$$v$$$ contains fewer than $$$5$$$ nodes, repeat the smallest value present in the subtree as many times as needed to complete the $$$5$$$ values.

Example
Input
7
1 2
1 3
2 4
2 5
3 6
3 7
9
1 4 10
1 5 3
1 2 6
2 2
1 6 8
1 7 8
2 3
1 1 100
2 1
Output
10 6 3 3 3 
8 8 0 0 0 
100 10 8 8 6
B. Google Search (Hard)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. In this version, $$$n, q \le 10^5$$$.

After years of competitive programming, Pacha is officially tired. Too many WAs, too many TLs, too many "elegant" data structures that only work in editorials. So he decided to do something different: build his own web search engine.

In a real search engine, searches are usually stored in a huge trie that grows with every new query. Pacha thought about doing it that way, and then remembered he had already suffered enough. To avoid dying with tries, he decided to reduce the problem to a simpler structure.

His search engine is modeled as a fixed tree with $$$n$$$ nodes. Each node represents a search category and stores a counter of how many times it has been searched. Initially, all counters are $$$0$$$.

The tree never changes shape or grows. The only thing that happens over time is that searches accumulate.

During $$$q$$$ days, events of two types are recorded:

  • Type $$$1$$$: a category receives new searches and its counter increases.
  • Type $$$2$$$: Pacha wants to know the $$$5$$$ most searched categories, in non-increasing order, within a part of his search engine represented by a subtree.

The tree is rooted at node $$$1$$$. The subtree of a node $$$v$$$ includes $$$v$$$ itself and all of its descendants.

Your task is to process all events and correctly answer every query.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$), the number of nodes of the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$), meaning there is an edge between $$$a_i$$$ and $$$b_i$$$. It is guaranteed that the edges form a tree.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of recorded events.

Each of the next $$$q$$$ lines describes an event. There are two possible types of events:

  • 1 $$$v$$$ $$$x$$$ — increase the counter of node $$$v$$$ by $$$x$$$ ($$$1 \le v \le n$$$, $$$1 \le x \le 10^3$$$).
  • 2 $$$v$$$ — query: report the $$$5$$$ largest values, in non-increasing order, within the subtree of $$$v$$$ ($$$1 \le v \le n$$$).
Output

For each query of type $$$2$$$, print a line with exactly $$$5$$$ integers in non-increasing order.

Note: if the subtree of node $$$v$$$ contains fewer than $$$5$$$ nodes, repeat the smallest value present in the subtree as many times as needed to complete the $$$5$$$ values.

Example
Input
7
1 2
1 3
2 4
2 5
3 6
3 7
9
1 4 10
1 5 3
1 2 6
2 2
1 6 8
1 7 8
2 3
1 1 100
2 1
Output
10 6 3 3 3 
8 8 0 0 0 
100 10 8 8 6
C. Geometry Killer
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pacha got bored of teaching computational geometry to the insabrossos, so he decided to put a Euclidean geometry problem in the SanSi Cup 2025.

In the figure, $$$AB$$$ is perpendicular to $$$BC$$$ and $$$AB = c$$$ units of length. $$$AC$$$ and $$$DB$$$ intersect at point $$$I$$$, and $$$IG$$$ is perpendicular to $$$BC$$$. Given that $$$DC = b$$$ units and $$$BC = a$$$ units, compute the length of $$$IG$$$.

Express the result with two numbers $$$p, q$$$ that represent the length of $$$IG$$$ as the irreducible fraction $$$p / q$$$ (it is guaranteed that the result is unique and expressible as an irreducible fraction). For example, $$$3/4$$$ is an irreducible fraction and $$$6/8$$$ is not.

Input

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

Each of the next $$$t$$$ lines contains $$$3$$$ integers $$$a, b, c$$$ ($$$1 \le a, b, c \le 10^9$$$).

Output

For each test case, print two integers $$$p, q$$$ representing the length of $$$IG$$$ as the irreducible fraction $$$p / q$$$.

Example
Input
1
2 2 2
Output
1 1
D. Pizzas
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a perfectly circular pizza. You will make straight cuts: each cut is an infinite straight line (like the complete path of a knife) that goes through the pizza.

Given a natural number $$$N$$$, your goal is to determine the minimum number of straight cuts needed to obtain exactly $$$N$$$ pieces of pizza, or print $$$-1$$$ if it is impossible. The pieces do not need to have the same size or the same shape.

Input

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

Each of the next $$$T$$$ lines contains an integer $$$N$$$ ($$$1 \le N \le 10^5$$$).

Output

For each test case, print an integer: the minimum number of straight cuts needed to obtain exactly $$$N$$$ pieces, or $$$-1$$$ if it is not possible.

Example
Input
3
3
10
1
Output
2
4
0
E. The Food Route
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While Tarija has the famous wine route, in Cochabamba Mateo, Ale, Harrison and Thiago, four friends from UMSS, decided to create something much more urgent: The Food Route.

They have a list of $$$n$$$ food stops in a fixed order (the route cannot be changed). At each stop $$$i$$$, an amount $$$a_i$$$ of food is eaten.

To survive the route, they decide to split it into $$$4$$$ consecutive segments, one for each friend. Each segment must be non-empty, must respect the original order and, together, the four segments must cover the whole route.

The "load" of a person is the sum of the food in their segment. For each segment the sum of its elements is computed, obtaining $$$S_1, S_2, S_3$$$ and $$$S_4$$$. Since nobody wants to end up sleeping in a flowerbed on América Avenue, they want to split the route as fairly as possible.

The goal is to choose the split that minimizes $$$\max(S_1, S_2, S_3, S_4) - \min(S_1, S_2, S_3, S_4)$$$.

Print the minimum possible value of that difference.

Input

The first line contains an integer $$$n$$$ ($$$4 \le n \le 10^5$$$), the number of food stops.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), where each number is the amount of food eaten at that stop.

Output

Print a single integer: the minimum possible difference between the largest and the smallest sum when splitting the array into 4 non-empty contiguous subarrays.

Examples
Input
6
1 3 2 4 6 5
Output
2
Input
10
28 21 54 10 5 19 2 30 40 1
Output
23
Input
9
23 10 31 55 70 21 10 34 45
Output
36
F. Tuesday Night Fever (Easy)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. In this version, $$$n \le 10^6$$$.

Armando is a very special being. Not only because he shines a little brighter on Tuesday nights, but because he has two incredible powers... which, unfortunately, only work on Tuesday nights.

His powers are the following:

  1. He can find a party with exactly the number of people he wants.
  2. Every time he enters a party, all the people present start greeting each other, one by one. Each greeting consists of both people solemnly saying: — maestro.

Armando, being very, very special (and a bit obsessive), wants to hear the word maestro exactly $$$n$$$ times during one Tuesday night.

But there is a serious problem. When Wednesday arrives, his powers disappear completely. So Armando needs to get exactly $$$n$$$ maestros attending the smallest possible number of parties.

Armando can attend several parties during the night, and at each one he can choose how many people there will be. The total number of maestros he hears is the sum of the maestros generated at all the parties he attends.

Your task is to help Armando. Given a number $$$n$$$, determine the minimum number of parties he needs to attend to hear exactly $$$n$$$ maestros.

Input

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

Each of the next $$$t$$$ lines contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the exact number of maestros Armando wants to hear.

Output

For each test case, print a single integer: the minimum number of parties needed to get exactly $$$n$$$ maestros.

Example
Input
5
1
2
3
42
10
Output
1
2
1
2
1
Note

For $$$n = 10$$$, Armando can attend a single party with $$$5$$$ people:

  • Armando — maestro — Chamir
  • Armando — maestro — Geordie Maddie
  • Armando — maestro — Mishi
  • Armando — maestro — Oliver
  • Chamir — maestro — Geordie Maddie
  • Chamir — maestro — Mishi
  • Chamir — maestro — Oliver
  • Geordie Maddie — maestro — Mishi
  • Geordie Maddie — maestro — Oliver
  • Mishi — maestro — Oliver
G. Tuesday Night Fever (Hard)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. In this version, $$$n \le 10^{12}$$$.

Armando is a very special being. Not only because he shines a little brighter on Tuesday nights, but because he has two incredible powers... which, unfortunately, only work on Tuesday nights.

His powers are the following:

  1. He can find a party with exactly the number of people he wants.
  2. Every time he enters a party, all the people present start greeting each other, one by one. Each greeting consists of both people solemnly saying: — maestro.

Armando, being very, very special (and a bit obsessive), wants to hear the word maestro exactly $$$n$$$ times during one Tuesday night.

But there is a serious problem. When Wednesday arrives, his powers disappear completely. So Armando needs to get exactly $$$n$$$ maestros attending the smallest possible number of parties.

Armando can attend several parties during the night, and at each one he can choose how many people there will be. The total number of maestros he hears is the sum of the maestros generated at all the parties he attends.

Your task is to help Armando. Given a number $$$n$$$, determine the minimum number of parties he needs to attend to hear exactly $$$n$$$ maestros.

Input

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

Each of the next $$$t$$$ lines contains an integer $$$n$$$ ($$$1 \le n \le 10^{12}$$$), the exact number of maestros Armando wants to hear.

Output

For each test case, print a single integer: the minimum number of parties needed to get exactly $$$n$$$ maestros.

Example
Input
5
1
2
3
42
10
Output
1
2
1
2
1
Note

For $$$n = 10$$$, Armando can attend a single party with $$$5$$$ people:

  • Armando — maestro — Chamir
  • Armando — maestro — Geordie Maddie
  • Armando — maestro — Mishi
  • Armando — maestro — Oliver
  • Chamir — maestro — Geordie Maddie
  • Chamir — maestro — Mishi
  • Chamir — maestro — Oliver
  • Geordie Maddie — maestro — Mishi
  • Geordie Maddie — maestro — Oliver
  • Mishi — maestro — Oliver
H. The Hard One
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pacha wanted to propose a super hard problem so that Nico could not solve it, but Pacha ran out of time, so now you have this problem titled The Hard One.

Pacha gives you two even integers $$$a$$$ and $$$b$$$, and assures you that there exists a number $$$x$$$ satisfying a very particular condition: the distance between $$$x$$$ and $$$a$$$ is exactly the same as the distance between $$$x$$$ and $$$b$$$.

Formally: $$$|x - a| = |x - b|$$$.

Pacha wants to find that number $$$x$$$. It is guaranteed that the answer is a unique integer and that it always exists.

Input

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

Each of the next $$$t$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$-10^3 \le a, b \le 10^3$$$, $$$a \ne b$$$).

Output

For each test case, print a single number $$$x$$$ such that $$$|x - a| = |x - b|$$$.

Example
Input
3
-2 2
0 2
10 20
Output
0
1
15