Concurso de programación ANIEI 2023
A. Akira
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the year 3012, in some place of Neo Mexico. All the pieces of Akira are awakening, each one making a big sphere of light in the process.

Every sphere of light consumes everything it touches, which is why it has been considered a Level 1 catastrophe all the volume delimited by the sphere. However, as time passes by, the spheres will become so big that they start to intersect one another, the moment when two spheres intersect they will be more close to summoning Akira, so they will be categorized as a Level 2 catastrophe. In general, the moment when a level $$$A$$$ catastrophe intersects a Level $$$B$$$ catastrophe they will become a Level $$$A$$$ + $$$B$$$ catastrophe.

You know where are all the pieces of Akira and the number of kilometers the spheres expand each second. Determine the minimum time it will take to a catastrophe of level $$$K$$$ or greater to be present.

Input

The first line contains the number of independent test cases $$$T$$$ $$$(1≤T≤200)$$$. Next $$$T$$$ lines contain a description of test cases.

The first line of description of each test case contains the number of pieces of Akira $$$N$$$ $$$(1≤N≤1000)$$$, a real number $$$M (1≤M≤100)$$$ indicating the number of kilometers that the sphere expand each second, and finally the level of catastrophe $$$K (1≤K≤N)$$$

The next N lines contain a pair of integers $$$X$$$, $$$Y$$$ $$$(-1e6≤X,Y≤1e6).$$$

Output

Print $$$T$$$ real numbers, each number on a separate line.

In $$$i-th$$$ line print answer for the $$$i-th$$$ case. Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{−6}$$$.

Examples
Input
1
1 1 1
0 0
Output
0
Input
1
4 1 2
0 0
0 2
500 500
500 100
Output
1.000000
Note

Even if the light consumes everything, we will always raise up.

B. Beautiful Binary String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Maria is solving a code puzzle to unlock an ancient treasure chest she found on a remote island. The puzzle is based on finding a special binary string called a "Beautiful Binary String." A Beautiful Binary String is a binary string with unique properties.

Maria has a partial binary string, but she needs to determine the maximum length of the Beautiful Binary String she can form, ensuring it complies with specific constraints. The string must have at most C0 '0's and at most C1 '1's, and it must not contain any substring consisting solely of '0's with more than M0 characters, or any substring consisting solely of '1's with more than M1 characters.

Given the values of C0, C1, M0, and M1, your task is to help Maria find the length of the largest Beautiful Binary String she can form.

Input

The input consists of a single line containing four integers separated by a space: C0 $$$(0 \leq C0 \leq 10^6)$$$, C1 $$$(0 \leq C1 \leq 10^6)$$$, M0 $$$(0 \leq M0 \leq 10^6)$$$, and M1 $$$(0 \leq M1 \leq 10^6)$$$.

Output

Print a single integer, which is the length of the largest Beautiful Binary String that can be formed. If it is not possible to form a Beautiful Binary String, print -1.

Examples
Input
10 10 10 10
Output
20
Input
10 1 1 1
Output
3
Input
2 2 3 3
Output
4

C. Cut the Magic Triangle
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the famous game The Legend of Pepe, Pepe is a forest elf who needs to save his kingdom from the evil Gadonorf. To achieve this, he needs the legendary artifact of the Tri-Power which is made of 3 magic triangles, the evil Gadonorf had the Triangle of muscles, the princess had the triangle of mathematics, and the hero had none, so he decided to create his own.

To create his triangle he needs to cut a triangle on a grid, the 'triangle' is made up of squares on the grid such that the top is only a square, and from the top to the bottom it has a number of squares in that row equal to the previous row plus 2, in such a way that they are connected in the shape of a triangle, generating 3 sides of equal length.

The power of a cut triangle is equal to the sum of the value in the cells, however, there are cells that are cursed with the ancient magic called 'rust', so a triangle that is 'rusted' will have 0 power.

Help Pepe know what is the greatest amount of power he can get for his magic triangle.

From the previous images, only the yellow triangle is valid.

Input

The first line of input contains an integer $$$N$$$ ($$$ 1 \leq N \leq 1000 $$$) representing the length of one side of the grid. Each of the next $$$N$$$ contains $$$N$$$ integers separated by a space $$$v_i$$$ ($$$ 1 \leq v_i \leq 10^{10} $$$ where the $$$j$$$-th integer of the $$$i$$$-th line represents the power of the cell in position $$$(i,j)$$$ of the grid, or -1 if that cell is rusted.

Output

Print a line with an integer that represents the greatest amount of power that a valid magic triangle can have on the grid.

Examples
Input
2
18 18
10 4
Output
18
Input
3
-1 4 10
-1 -1 3
2 2 6
Output
10
Input
4
8 -1 -1 -1
-1 -1 2 4
-1 -1 -1 8
-1 9 1 10
Output
10
Input
1
-1
Output
0

D. Determine Palindrome Message
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sara is a researcher who works on restoring ancient manuscripts. Recently, she found a mysterious manuscript with encrypted text. After careful study, Sara realized that the encrypted text is, in fact, a palindrome. However, the challenge is to determine if it's possible to rearrange the letters in the text to form a valid palindrome.

A palindrome is a word or phrase that reads the same forward and backward. In this case, Sara wants to figure out if she can rearrange the letters in the encrypted text to create a valid palindrome. This could help her decipher the hidden message in the ancient manuscript.

Given the encrypted text, your task is to help Sara determine if it's possible to rearrange the letters to form a valid palindrome. It's not necessary to use all the letters, but the rearrangement should allow for the creation of a valid palindrome.

Input

The input consists of a single line containing a string of lowercase characters. The string will have a length of up to $$$10^5$$$ characters.

Output

You should print "YES" if it's possible to rearrange the letters in the text to form a palindrome, or "NO" otherwise.

Examples
Input
3
aab
Output
YES
Input
3
abc
Output
NO
Input
6
aaaaaa
Output
YES

E. Exotic island
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Juan is a young entrepreneur who owns a souvenir shop on an exotic tourist island. The island is known for its white sandy beaches, crystal-clear waters, and a wide variety of local products that attract tourists from around the world. Juan works diligently in his shop, serving visitors and selling unique island souvenirs.

Each item in the shop has a price in dollars, and tourists purchase these items as mementos of their visit to the beautiful island. To facilitate the payment process and provide excellent customer service, Juan wants to calculate the minimum number of bills of a specific denomination needed to pay for an item of a given price.

Given an item with a price in dollars and a bill denomination, your task is to help Juan calculate the minimum number of bills of that denomination required to pay for the item.

Input

The input consists of two lines:

- The first line contains an integer $$$A$$$ $$$(1 \leq A \leq 10^9)$$$, which represents the bill denomination that Juan accepts in his shop.

- The second line contains an integer $$$B$$$ $$$(1 \leq B \leq 10^9)$$$, which represents the price of the item that a tourist wants to purchase.

Output

Print a single integer, which is the minimum number of bills of denomination $$$A$$$ needed to pay for the item of price $$$B$$$.

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

F. Far island treasure
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On a remote island, adventurers gather in search of a legendary treasure hidden deep within a mysterious jungle. The path to the treasure is full of challenges, and one of the most intriguing is the "Operation Challenge."

In this challenge, adventurers are given an initial array of size $$$10^9$$$, filled with virtual treasures (initially all zeros). They must then perform a series of $$$N$$$ operations on the array. Each operation is described by three numbers: $$$l$$$, $$$r$$$, and $$$x$$$, indicating that $$$x$$$ should be added to each element in the range from position $$$l$$$ to position $$$r$$$ (inclusive).

Once all operations have been completed, the next step of the challenge is to find the maximum treasure that can be obtained by adding all the elements of a subarray of size $$$K$$$. Adventurers must use their wits and skills to solve this puzzle and determine what the maximum treasure they can obtain is.

Given the array after all operations and the value of $$$K$$$, your task is to help adventurers find the maximum sum of the elements that can be obtained by taking a subarray of size $$$K$$$.

Input

The input consists of several lines:

- The first line contains two integers, $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ and $$$K$$$ $$$(1 \leq K \leq 10^9)$$$, representing the number of operations and the size of the subarray adventurers should consider, respectively.

- The following $$$N$$$ lines each contain three integers: $$$l$$$, $$$r$$$, and $$$x$$$ $$$(1 \leq l \leq r \leq 10^9, 1 \leq x \leq 1000)$$$, representing an operation on the array. Each operation indicates that $$$x$$$ should be added to each element in the range from position $$$l$$$ to position $$$r$$$ (inclusive).

Output

You should print a single integer, representing the maximum sum of the elements that can be obtained by taking a subarray of size $$$K$$$ after all operations have been performed.

Examples
Input
4 3
1 10 1
2 8 2
4 6 3
5 5 4
Output
22
Input
4 1
1 10 1
2 8 2
4 6 3
5 5 4
Output
10
Input
4 100
1 10 1
2 8 2
4 6 3
5 5 4
Output
37

G. Game of Coin Stacking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ana and Ernesto are playing an interesting game called "Coin Stacking." The game consists of $$$N$$$ stacks of coins, numbered from 1 to $$$N$$$. They start with an array of coin stacks, each with a specific number of coins. Players take turns making moves, starting with Ana.

In each turn, a player chooses a stack and takes a number of coins that is less than or equal to the number of coins in that stack. After each move, the number of coins in the stack is reduced by the amount taken. The players are extremely intelligent and always make the best possible decision in each turn.

The goal of the game is for Ana and Ernesto to try to sort the array of coin stacks at the end of the game in one of the following ways:

1. Ana wins if, at the end of the game, the array of coin stacks is sorted in a non-decreasing order.

2. Ernesto wins if, at the end of the game, the array of coin stacks is sorted in a non-increasing order.

3. If both conditions are met (the array is sorted in a non-decreasing and non-increasing order simultaneously), then both win.

Input

The first line of the input contains an integer $$$N$$$ $$$(1 \leq N \leq 1000000)$$$, the number of coin stacks.

The second line of the input contains $$$N$$$ integers separated by spaces, representing the number of coins in each stack. Each integer $$$A_i$$$ $$$(0 \leq A_i \leq 100)$$$ indicates the number of coins in stack $$$i$$$.

Output

Print "Ana" if Ana wins the game.

Print "Ernesto" if Ernesto wins the game.

Print "Both" if both win the game simultaneously.

Examples
Input
5
1 2 10 4 5
Output
Ana
Input
5
5 4 3 2 1
Output
Ernesto
Input
5
5 5 5 5 5
Output
Both

H. Happy Face
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One day our good friend Arthur Fleck went to Wayne's family mansion, determined to confirm the suspicions he had regarding his father's identity.

In the meantime, he found the little Bruce Wayne, who wasn't smiling. Of course, the comedian and friend of all the children wasn't happy about that. So he decided to play a game with him expecting to put on a happy face in Bruce.

The game consists of picking up balloons! To prevent someone to grab all the balloons in their first turn making the game boring, the rules are that you can only grab $$$A$$$, $$$B$$$ or $$$C$$$ balloons of one of the $$$K$$$ bundles of balloons each turn, and the first person who can not do this loses the game.

However Bruce is a very intelligent and very competitive boy, he will be mad if Arthur loses on purpose, so all the movements Arthur can make needs to be perfect to not upset Bruce, but Arthur will be sad if Bruce losses the game. Bruce will only be happy if he wins after Arthur and Bruce play an optimal game.

Input

A line denoting who of the players have the first turn, is either "Bruce" or "Arthur". The second line has 4 integers $$$A$$$, $$$B$$$, $$$C$$$, (1 ≤ $$$A$$$, $$$B$$$, $$$C$$$ ≤ 100) and $$$Q$$$ (1 ≤ $$$Q$$$ ≤ 1e5) describing the valid moves and the number of queries.

Then $$$Q$$$ queries follow, each query is described by two lines, the first contains an integer $$$K$$$ (1 ≤ $$$K$$$ ≤ 1e3) representing the number of bundles of ballons in the query, the second line contains $$$K$$$ integer numbers separated by a space, where the $$$i$$$-th number in the line represents the amount of balloons on the $$$i$$$-th bundle $$$K_i$$$ (1 ≤ $$$K_i$$$ ≤ 1e6).

Output

Print $$$Q$$$ lines, where the $$$i$$$-th contains the string "Happy Bruce" if Bruce wins the game on the $$$i$$$-th query, print the string "Sad Arthur" otherwise.

Examples
Input
Bruce
7 1 3 2
1
9
1
6
Output
Happy Bruce
Sad Arthur
Input
Arthur
4 3 8 1
2
903 69
Output
Sad Arthur
Note

Solving problems is fun and I'm tired of pretending that it's not.

I. Inspecting the Scores
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day Franco was waiting for the new game, Coding Hero. It is a two-player game so he decided to play it with his good friend Rafa.

This game consists of several team matches where there is a programming problem which they had to solve as quickly as possible, they started with a score equal to 1 and due to the combo breaker dynamics that the game has, this score is multiplied each time a player solves a problem.

When Franco solves a problem the score they had is multiplied by $$$A$$$, when Rafa solves a problem the score is multiplied by $$$B$$$, there could be cases where the problem is so difficult that no one could solve it, in that case, they just go on to the next problem without losing or gaining points.

They were so obsessed with the game that they played and played, and they realized that their scores vary a lot depending on who solves the problems, Grecia with a lot of curiosity, began to think about what would be the sum of scores of all possible outcomes.

Two results are different if in some games the person who solved the problem is different, help Grecia to know what is the sum of the scores of all possible games! Since the number can be very large, print it modulo $$$10^9+7$$$.

Input

An integer $$$T$$$ ($$$ 1 \leq T \leq 10^5 $$$) that indicates the number of cases you have to answer, followed by $$$T$$$ lines each defined by 3 integers $$$N$$$, $$$A$$$ and $$$B$$$ ( $$$ 1 \leq N \leq 1000, 1 \leq A, B \leq 10^8 $$$). Which refer to the number of matches in the game, Franco's multiplier and Rafa's multiplier.

Output

$$$T$$$ lines each, where the $$$i$$$-th line contains an integer, representing the answer of $$$i$$$-th case from the input.

Examples
Input
1
1 6 9
Output
16
Input
1
2 8 4
Output
169
Input
3
6 2 7
10 3 8
9 1 1
Output
1000000
917363797
19683

J. Juan Jo Hiking Trip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Juan José is organizing an exciting hiking trip and plans to take a group of $$$K$$$ people with him. Each person $$$i$$$ has a backpack with a fixed capacity of $$$B_i$$$ units of weight. The goal is to carry provisions for the trip, but Juan José wants to do it efficiently and maximize the total number of the provisions carried by the group.

Juan José has a list of $$$M$$$ different provisions. Each provision $$$i$$$ has a weight $$$W_i$$$. The weight of a provision represents the amount of space it occupies in the backpack. The backpack capacities are given in an array of size $$$K$$$, where the $$$i$$$-th element ($$$K_i$$$) represents the capacity of the backpack for person $$$i$$$. Juan José needs to decide how to distribute the provisions among the people's backpacks in a way that maximizes the total number of provisions carried by the group and complies with the backpacks' capacity constraints.

Since Juan José is a skilled programmer, he needs your help to write a program that finds the optimal distribution of provisions to maximize the total value.

Input

The first line of input will contain two integers separated by a space: $$$K$$$ $$$(1 \leq K \leq 15)$$$, the number of people in the group, and $$$M$$$ $$$(1 \leq M \leq 15)$$$, the number of available provisions.

The following line will contain $$$K$$$ integers $$$K_i$$$ $$$(1 \leq K_i \leq 15)$$$ separated by spaces, representing the backpack capacities for each person in the group.

The following line will contain $$$M$$$ integers $$$M_i$$$ $$$(1 \leq M_i \leq 15)$$$ separated by spaces, representing the weights of each provision.

Output

You should print a single integer that represents the maximum total of provisions that the group can carry on the hiking trip without exceeding the capacity of anyone's backpack.

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

Условие недоступно на русском языке
L. Lucia's Treasure
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Lucía is a young adventurer who has discovered an ancient map that appears to lead to a hidden treasure. The map has a series of mysterious clues, and one of the clues refers to a special number related to her treasure hunt. According to the map, Lucía must find the smallest multiple of a positive integer $$$X$$$ that is a perfect square.

A perfect square is an integer that can be expressed as the square of another integer. For example, $$$1$$$, $$$4$$$, $$$9$$$, and $$$16$$$ are examples of perfect squares.

Lucía is excited about her treasure hunt and needs your help to determine the value of the smallest multiple of $$$X$$$ that meets this special condition. If she can find this number, she can advance in her quest and get closer to the hidden treasure.

Given the value of $$$X$$$, your task is to find the smallest multiple of $$$X$$$ that is a perfect square or indicate that no such multiple exists.

Input

The input consists of a single line containing a positive integer $$$X$$$ $$$(1 \leq X \leq 10^9)$$$.

Output

You should print a single integer, which is the smallest multiple of $$$X$$$ that is a perfect square. It's guaranteed that such multiple exists.

Examples
Input
3
Output
9
Input
16
Output
16
Input
12
Output
36