2025 ICPC Gran Premio de Mexico 2da Fecha
A. Arithmetica's problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the land of Arithmetica, the wise mathematician Numeron is known for solving intricate numerical puzzles. One day, Numeron encounters a problem involving a range of numbers and a special integer $$$K$$$. The challenge is to determine how many numbers within a given range are multiples of $$$K$$$. Your task is to help Numeron by calculating the number of multiples of $$$K$$$ within the interval $$$[L, R]$$$.

Input

The first line contains three integers $$$L$$$, $$$R$$$, and $$$K$$$ ($$$1 \leq L \leq R \leq 1000$$$, $$$1 \leq K \leq 1000$$$), representing the start and end of the interval and the special integer, respectively.

Output

Output a single integer representing the count of numbers within the interval $$$[L, R]$$$ that are multiples of $$$K$$$.

Examples
Input
1 10 2
Output
5
Input
1 10 3
Output
3
Input
13 27 5
Output
3

B. Building Skyscrapers
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Legendary Huron is planning the construction of $$$n$$$ skyscrapers on a major street in Huronland that runs from west to east. The final skyline will be an array of positive integers $$$A = [a_1, a_2, \dots, a_n]$$$, where $$$a_i$$$ is the height of the $$$i$$$-th skyscraper from the west. The order of construction and the heights are yet to be decided. For safety reasons, only one skyscraper can be built at a time.

After all skyscrapers are completed, the Tourism Office will promote each one using a panoramic photo. For each skyscraper $$$i$$$, the office selects the longest contiguous segment of skyscrapers that includes $$$i$$$, such that the maximum height in the segment is $$$a_i$$$, and takes a photo of such segment. A photo is considered successful if:

  1. Skyscraper $$$i$$$ is the last one built among all skyscrapers in the photo.
  2. Let $$$k$$$ be the number of skyscrapers in the segment and $$$d$$$ the absolute difference between the maximum and second maximum heights in it. Then $$$d$$$ must satisfy $$$l_k \leq d \leq r_k$$$, where $$$l_k$$$ and $$$r_k$$$ are input integers. If the segment contains only one skyscraper, the second maximum is considered $$$0$$$. For example, the segment $$$[4, 9, 1, 3]$$$ has $$$d = 5$$$; the segment $$$[2, 1, 2]$$$ has $$$d = 0$$$; and the segment $$$[4]$$$ has $$$d = 4$$$.

The Tourism Office asks the Legendary Huron to assign positive heights and a construction order so that all $$$n$$$ photos are successful. Two plans are different if the heights or construction order differ. Determine the number of such valid plans, modulo $$$998244353$$$.

Input

The first line contains $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$).

Then $$$n$$$ lines follows, where the $$$(i+1)$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \leq l_i \leq r_i \leq 10^9$$$).

Output

Print the answer modulo $$$998244353$$$.

Examples
Input
1
1 10
Output
10
Input
1
0 0
Output
0
Input
2
1 4
5 7
Output
24
Input
3
1 1
2 2
3 3
Output
6

C. Chicken Jockey
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the world of Minecraft! Made completely out of cubes. In here you met Steve, the architect of this world. Right now Steve is busy building a railway and you have decided to help him, being the selfless and helpful programmer you always are.

In particular he wants to build the railway on a straight line of $$$N$$$ cubes. But here the terrain is very messy, so every cube in the line may have a different elevation. In particular the first cube will have an elevation of $$$a_1$$$, the second cube will have an elevation of $$$a_2$$$, etc... up to $$$a_N$$$ for the elevation of the $$$N$$$-th cube.

In this Minecraft world a railway is made out of multiple, not necessarily connected, tracks. A track expands over a contiguous set of cubes of size at least $$$2$$$. No cube can be in more than one track, meaning no tracks ever intersect.

Because Steve is a really lazy guy, he wants to make sure his railway is planned to perfection before starting. He asks you to help him calculate the number of ways the railway can be made, with the added condition that a track has to start and end at the same elevation, because "You can only find Diamonds at the right level".

Since Steve is a considerate person it's not necessary to cover the $$$N$$$ cubes with tracks for a valid railway configuration. You can also decide not to create any track at all.

Input

On the first line a number $$$N$$$ ($$$1 \leq N \leq 3 \times 10^6$$$) the length of the line where the railway will be. On the second line $$$N$$$ numbers $$$a_1,a_2,...a_N$$$ ($$$1 \leq a_i \leq 10^5$$$) describing the elevation of each block in the line.

Output

Just one number, the ways the railway can be set. As this number can be very big, print it modulo $$$998244353$$$

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

"And the universe said I love you because you are love."

For the first testcase the valid configurations are the following:

  • A track that starts on the first cube and ends on the third, both with elevation equal to $$$1$$$.
  • A track that starts on the second cube and ends on the fourth, both with elevation equal to $$$2$$$.
  • Building no tracks.

For the second testcase the only valid track configuration for the railway is to build no tracks at all.

This statement has been modified to include the clarifications made during the competition.

D. Discovering Graphlandia
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the mystical realm of Graphlandia, each city is represented by a node in a vast network of roads, forming a graph. Each city is infused with a magical energy level, attracting adventurers from all corners of the world. As an adventurer, your task is to determine how many cities you can explore starting from each city, with the constraint that you may only travel to cities with an energy level less than or equal to the starting city's level.

The challenge is to calculate, for each city, the number of cities that can be reached under these conditions.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^6$$$, $$$0 \leq M \leq 10^6$$$), representing the number of cities (nodes) and the number of roads (edges) respectively.

The second line contains $$$N$$$ integers $$$e_1, e_2, \ldots, e_N$$$ ($$$1 \leq e_i \leq 10^6$$$), where $$$e_i$$$ is the energy level of city $$$i$$$.

The next $$$M$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$, $$$u \neq v$$$), representing a bidirectional road between cities $$$u$$$ and $$$v$$$. Each pair of cities is connected by at most one road.

Output

Output $$$N$$$ lines, each containing a single integer. The $$$i$$$-th line should contain the number of cities that can be visited starting from city $$$i$$$, following the movement rules.

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

E. Esoteric Computer Architecture
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Have you heard of esoteric programming languages? These are languages designed for experimentation, artistic expression, or humor, rather than practical use.

Inspired by this idea, Ángel designed a simulated computer with an esoteric computer architecture for his final project in the Computer Architecture class. Unlike conventional computers, Ángel's machine represents data using the decimal numeral system at the hardware level.

To demonstrate his project, Ángel plans to run several programs. One of them transforms an array $$$A = [a_1, a_2, \dots, a_n]$$$ into an array $$$B = [b_1, b_2, \dots, b_n]$$$ using only the swap instruction, which Ángel included as a native operation.

However, Ángel discovered a critical bug in the swap instruction. When swapping two values, the instruction not only exchanges them but also trims the operand with more digits to match the number of digits of the shorter operand by removing the most significant digits.

For example, swapping positions $$$2$$$ and $$$4$$$ in $$$[5,13564,2,23]$$$ results in $$$[5,23,2,64]$$$ ($$$13564$$$ and $$$23$$$ are swapped, and $$$13564$$$ becomes $$$64$$$ to match the two-digit length of $$$23$$$).

After further investigation, Ángel realized that the bug was worse than he had initially thought. The swap instruction preserves leading zeros after a number is trimmed, and the leading zeros persist across the swap instruction unless they are trimmed to match the length of a shorter number.

For example, swapping positions $$$1$$$ and $$$2$$$ in $$$[101,11,123]$$$, results in $$$[11, 01, 123]$$$, and swapping positions $$$2$$$ and $$$3$$$ in the previous array, results in $$$[11, 23, 01]$$$.

Ángel traced the bug to a faulty hardware simulation. Rebuilding it would take too long, so he asks for your help: transform $$$A$$$ into $$$B$$$ using at most $$$2n$$$ buggy swaps, such that the final array does not contain any leading zeros (but it may contain leading zeros during intermediate steps), since his teacher will consider it as a serious flaw if the final array contains any leading zero.

Input

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

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

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$0 \leq a_i \lt 10^9$$$).

The third line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ ($$$0 \leq b_i \lt 10^9$$$).

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

Output

For each test case, print $$$-1$$$ if it is not possible to transform $$$A$$$ into $$$B$$$ using at most $$$2n$$$ swaps.

Otherwise, print the number of times to perform a buggy swap instruction in the first line of the output. This number should be in the range $$$[0,2n]$$$. Then print one line per swap instruction in order. In each line, print two integers — the indices of positions to swap.

If there are multiple solutions, print any of them.

Example
Input
5
4
5 13564 2 23
2 23 5 64
2
1 21
2 1
4
101 11 123 1
11 23 1 1
1
0
0
2
101 11
11 1
Output
2
2 4
3 1
-1
3
1 2
2 3
3 4
0
-1

F. Fixing logs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Finally Monster Hunter Wilds has released and Sebastian has been playing non stop since then. On Monster Hunter you go on hunts to kill a monster and gather its materials. There are many kind of weapons you can use in Monster Hunter, and Wilds now allows you to use a principal weapon and a secondary weapon in each hunt!

Sebastian has been keeping a log of how many times he has used each weapon as his main one, and how many times he has used it as his secondary, but due to being too distracted playing he might have made some mistakes. He has asked you to help him figure it out, while he keeps playing.

Given the list of logs describing how many times each weapon has been used as main and as secondary, decide if it's possible to have gotten these values given that in each mission a primary and a secondary weapon were used, and they were different. If it's impossible to have a valid assignment from the logs, compute the least amount of changes needed to make it a viable list. A change is considered as either increasing or decreasing any number in the list by one.

Input

On the first line a number $$$N$$$ ($$$2\leq N \leq 10^6$$$) - the number of weapons.

On the next $$$N$$$ lines, two numbers $$$a_i$$$ and $$$b_i$$$ ($$$0\leq a_i, b_i\leq 10^6$$$) - the number of times the $$$i$$$-th weapon was used as primary and secondary, respectively.

Output

An integer, $$$0$$$ in case the list already provides a possible assignment, otherwise the number of changes necessary to make it a viable list.

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

"By order of the guild, hunt this problem"

G. Grandmapocalipse
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Oh no! Your cookie business has grown too successful, and you have mistreated the grandmas so much that you have awakened their fury, triggering the Grandmapocalypse. The only way to stop them is to travel to the milk sea of the chocolate islands, and make a ritual to the golden cookie.

The ritual consists of choosing 3 chocolate islands such that the golden cookie is inside the triangle they form when seen from above (it has to be completely inside, so it won't work if the cookie is collinear with two of the islands).

Sadly, due to indiscriminating chocolate mining from your side, the cookie islands have grown smaller and most of them are under the milk sea. But there's still hope! You know the location of each island (given by $$$x$$$ and $$$y$$$ coordinates), its height (given by $$$z$$$), and know that the Grandmatriarch is drinking the milk sea such that its height will go down in a uniform way of 1 meter per hour. Currently, the milk sea is $$$h$$$ meters tall, and you want to know exactly how many hours will pass before you can do the ritual. A cookie is available for you to pick if its height is greater than or equal to the milk sea height.

Your answer is considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.

Input

On the first line, an integer $$$N$$$ $$$(1\leq N \leq 10^5)$$$ and a real number $$$h$$$ $$$(1\leq h \leq 10^9)$$$, the number of chocolate islands and the height of the sea at the start, respectively.

On the next $$$N$$$ lines, 3 real numbers $$$x_i,y_i,z_i$$$ ($$$-10^9\leq x_i,y_i,z_i\leq 10^9$$$), indicating the coordinates of the $$$i$$$-th island.

On the last line 2 real numbers, $$$a$$$ and $$$b$$$ ($$$-10^9\leq a, b\leq 10^9$$$), the coordinates of the golden cookie.

All coordinates will be given with two digits after the decimal point. It is guaranteed that if two islands have the same $$$x$$$ and $$$y$$$ coordinates, then their height ($$$z$$$) it's different.

Output

A real number, indicating how many hours will have to pass before you can do the ritual. If you won't be able to defeat the grandmapocalypse, print "-1".

Your answer is considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.

Examples
Input
4 10.00
1.00 1.00 7.00
3.00 1.00 11.00
3.00 3.00 -2.00
1.00 3.00 15.00
2.50 2.50
Output
12.0000000000
Input
3 10.00
1.00 1.00 20.00
3.00 1.00 6.47
2.00 3.00 2.45
5.00 3.00
Output
-1
Note

"A local news station runs a 10-minute segment about your cookies. Success!"

This statement has been modified to include the clarifications made during the competition.

H. Hathsin's piths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kelsier has been trapped inside the deadly pits of Hathsin. He was sure he would die inside, but he had awakened his allomantic powers and could try to escape now! His powers allow him, among other things, to pull himself towards or push himself from metal rods, and he plans to use them to their full potential.

The pits can be seen as a 2D plane that goes from $$$0$$$ to $$$-\inf$$$ in the Y axis, and from $$$-\inf$$$ to $$$\inf$$$ in the $$$X$$$ axis. The wall is full of ledges, some of which have metal rods. Kelsier can pull himself into any metal rod that's at most $$$k$$$ units away, and can push himself from any ledge with a metal rod to another ledge that's at most $$$h$$$ units away or to the surface if it's at most $$$h$$$ units away. Kelsier will have escaped if he reaches the surface, which is represented as an infinite line from $$$(-\inf,0)$$$ to $$$(\inf,0)$$$

Given the position of the ledges and whether they have metal rods or not, help Kelsier find the minimum number of pulls and pushes he will have to do to escape.

Input

On the first line, 3 integers $$$N,h,k$$$ ($$$1\leq N \leq 10^4, 1\leq h,k \leq 10^9$$$) representing the number of ledges, how far away Kelsier can push himself, and how far he can pull himself, respectively.

On the next $$$N$$$ lines, 3 integers, $$$x_i, y_i, z_i$$$ ($$$-10^9\leq x_i \leq 10^9, -10^9\leq y_i \leq 0$$$, $$$z_i\in \{0,1\}$$$). The first two numbers indicate that there is a ledge in $$$(x_i,y_i)$$$, and $$$z_i$$$ will be $$$1$$$ if the ledge has a metal rod, or $$$0$$$ otherwise.

In the last line, 2 integers $$$a,b$$$ ($$$-10^9\leq a \leq 10^9, -10^9\leq b \leq 0$$$) indicating that Kelsier starts in position($$$a,b$$$). There will always be a ledge in the starting coordinates.

Output

Just a number $$$m$$$, the minimum number of pushes and pulls Kelsier has to do to escape. If there is no way to escape, print $$$-1$$$

Examples
Input
5 1 3
1 -3 0
2 -2 0
-2 -3 1
0 -1 1
-1 -2 0
1 -3
Output
2
Input
5 1 3
1 -3 0
2 -2 0
-2 -3 1
0 -1 0
-1 -2 0
1 -3
Output
-1
Input
5 1 3
1 0 0
2 -2 0
-2 -3 1
0 -1 1
-1 -2 0
1 0
Output
0
Note

"survive"

This statement has been modified to include the clarifications made during the competition.

I. Inifinitus Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the realm of Calculus, the legendary mathematician Infinitus is fascinated by a peculiar infinite sequence. The sequence begins with an endless series of the number $$$X$$$. In each iteration, Infinitus inserts the sum of each consecutive pair of numbers between them, transforming the sequence as follows:

- Initially in iteration one, if $$$X = 5$$$ the sequence looks like this: $$$5, 5, 5, 5, \ldots $$$

- After the second iteration: $$$5, 10, 5, 10, 5, 10, \ldots$$$

- After the third iteration: $$$5, 15, 10, 15, 5, 15, 10, 15, 5, \ldots $$$

Your task is to answer $$$Q$$$ queries. For each query, given two numbers $$$X$$$ and $$$K$$$, determine the first iteration in which a number greater or equal to $$$K$$$ appears in the sequence starting with $$$X$$$.

Input

- The first line contains an integer $$$Q$$$ $$$1 \leq Q \leq 1,000$$$, the number of queries.

- Each of the next $$$Q$$$ lines contains two integers $$$X$$$ and $$$K$$$ $$$( 1 \leq X \leq 1,000 ), ( 1 \leq K \leq 10^9 )$$$.

Output

For each query, output a single integer representing the first iteration where a number greater than $$$K$$$ appears in the sequence.

Examples
Input
3
5 1
5 10
5 15
Output
1
2
3
Input
1
1 5
Output
4
Note

This statement has been modified to include the clarifications made during the competition.

J. Justice for the Underdogs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You just looked at a flier for the upcoming inter-university bowling tournament. Your university is looking for a team to represent it, but you're still hesitating on applying as you think you're not good enough. Meanwhile, you got more interested in the problem of how the team should be formed.

For the tournament, a team should consist of $$$K$$$ people, and you know that $$$N$$$ participants from your university have applied to represent it. You're totally convinced that the skill of a team is determined by its weakest link, meaning the team member with the lowest ability. Thus, for a team $$$T$$$ where each member has a bowling ability of $$$a_i$$$ ($$$1 \leq i \leq |T|$$$), the total ability of the team is the minimum across all members ($$$T_a = min(a_1, a_2, \dots a_{|T|}$$$). Your university has a special characteristic where the abilities of the $$$N$$$ registered participants are unique, thus forming a permutation of integers from $$$1 \dots N$$$.

You want to know the sum of the abilities of each of the representing teams of $$$K$$$ members that could be formed from the $$$N$$$ registered participants, taking into account how the team's ability is calculated.

You would like to compute the previous value for a lot of pairs of team size ($$$K$$$) and registered participants ($$$N$$$), but you got to do it fast before your university's team gets selected!

Input

In the first line, you're given an integer $$$Q$$$ $$$-$$$ ($$$1 \leq Q \leq 10^5$$$) $$$-$$$ the number of queries you will be asked.

For each of the next $$$Q$$$ lines, you will get two integers $$$N$$$ and $$$K$$$ $$$-$$$ ($$$1\leq K \leq N \leq 10^6$$$) $$$-$$$ the number of registered participants and the size that the teams should have, respectively.

Output

For each of the $$$Q$$$ lines, you should print one integer, the answer to the query. Since the answer can be pretty big, print it modulo $$$998244353$$$.

Example
Input
5
5 3
2 1
11 4
23583 237
1000000 35624
Output
15
3
792
854389980
475464584

K. K. K. Slider's concert
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

K K slider, the famous song writer is going to come to you village! You have decided to buy new shoes for all of your NPCs vilagers. You have a tight budget of just $$$k$$$ bells, and on the store every shoe is at a different price, not only that but left and right shoes are sold at different prices. So given the price of every shoe, find the maximum amount of pair of shoes you can buy. (A pair of shoes is formed from a left and a right shoe, The NPCs aren't so picky, so the pair of shoes doesn;t have to be of the same kind)

Input

On the first line two numbers, $$$N$$$ and $$$k$$$. ($$$1\leq N \leq 10^5, 0\leq k \leq 2*10^9$$$) Indicating there are $$$N$$$ left shoes, and $$$N$$$ right shoes. $$$K$$$ is the number of bells you have. In the next line $$$N$$$ numbers between $$$0$$$ and $$$10000$$$ the cost of each right shoe in bells. In the next line $$$N$$$ numbers between $$$0$$$ and $$$10000$$$ the cost of each left shoe in bells.

Output

Just a number indicating how many pair of shoes you can get.

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

"But We Don't Do Things Because They Are Easy Hm? We Do Them Because They Are Profitable." -Tom nook.

L. Lemmings's Path
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the whimsical country of $$$Ratania$$$, there are $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$. The cities are connected by $$$n - 1$$$ roads, forming a $$$tree$$$.

Each city contains a single parenthesis character, either ''('' or '')''.

The inhabitants of Ratania, known as $$$Los$$$ $$$Ratones$$$, want to place $$$magical portals$$$ between pairs of cities. A portal can only be placed between two $$$distinct$$$ cities $$$u$$$ and $$$v$$$ if the path from $$$u$$$ to $$$v$$$ (following roads through the tree) forms a balanced parentheses sequence, when concatenating the characters of all cities along the path (including both endpoints).

A balanced parentheses sequence is defined as:

- Every prefix of the sequence contains at least as many ''('' as '')''.

- The total number of ''('' is $$$equal$$$ to the number of '')''.

$$$Los$$$ $$$Ratones$$$, however, are currently busy training for a prestigious international tournament, and they simply don't have time to figure this out themselves. That's why they've turned to you — a legendary expert in tree data structures and parentheses sorcery.

They want to know:

How many different portals can they place?

Input

The first line of input contains one integer, $$$N$$$ $$$(1 \leq N \leq 100000)$$$, the number of cities in Ratania

The second line contains $$$N$$$ characters representing what each citie contain ''('' or '')''

Each of the next $$$N-1$$$ lines contains two integers $$$X$$$ and $$$Y$$$ $$$(1 \leq X, Y \leq N,\ X \ne Y)$$$, meaning there's a road betwen $$$X$$$ and $$$Y$$$

Output

The number of different portals that they can place

Examples
Input
5
(()))
1 2
1 3
3 4
3 5
Output
3
Input
6
((()))
1 2
1 3
1 4
4 5
4 6
Output
5
Input
8
)))()(((
1 2
2 3
3 4
4 5
5 6
6 7
7 8
Output
6