• Memory Limit: 256MB
• Time Limit: 4sec

Nima and Sina are searching for a bag full of money. They know the money has been hidden in a grave in the cemetery, but they don't know which grave it is.

Nima has a friend in the Civil Registry Office, and with the help of his friend, he gathered a list of people who are buried in this cemetery. Meanwhile, Sina ran into the cemetery and wrote down all the grave names he saw. They noticed Sina's list has one name more than Nima's list. They believe there is exactly one grave that is not registered in the Civil Registry Office, and the money is hidden in it. They want you to find its name; If you help them you have the chance to get $4,500,000$ Chugh from the bag.

Input🔗

The first line of input contains the integer $N$, the number of names in Sina's list.

Each of the following $N$ lines contains the names of grave names.

The additional $N-1$ lines contain the names of people in Nima's list.

All the names will consist of at least one and at most $20$ lowercase letters of the English alphabet. The names in a list won’t necessarily be unique.

$1 \le N \le 100\ 000$

Output🔗

The first and only line of output must contain the name of the fake grave.

Sample Input 1🔗

3
stanton
karimi
bagheri
bagheri
karimi

Sample Output 1🔗

stanton

Sample Input 2🔗

4
nimaei
sinaei
nimaei
gol
sinaei
gol
nimaei

Sample Output 2🔗

nimaei

• Memory Limit: 256MB
• Time Limit: 1sec

The annual ICPC selection competition for students enrolled in Iran University of Science and Technology takes place tomorrow! This year, each team consists of $K$ students (Recent years there has been a lot of changes in the regulations, so this makes the change of the number of team members quite expectable!).

There are $N$ excited students, waiting in queue to register for the ICPC. The first team will consist of the first $K$ students in the queue, the second team the following $K$ students and so on... ($N$ will be divisible by $K$).

Dr. Parisina has estimated the skill of each player with an integer. She would like to have the $K$ strongest players in the first team, the following $K$ strongest in the second team, and so on. So Dr. Parisina decided to shift the students standing in the queue so that she achieves her goal. The way she shifts them is that she tells a student to step out of the queue and go back in the queue before another student or to go to the front of the queue (So she can move anyone to anywhere). It takes her one minute to do this. Her class will be started soon, so Dr. Parisina needs to achieve her goal as soon as possible. Help Dr. Parisina determine the minimal number of minutes necessary for her to achieve her goal.

Input🔗

The first line of input contains the integers $N$ and $K$ The second line contains $N$ space-separated integers $v_i$ - the number denotes the skill of the $i$-th player standing in the queue. Skill levels are from the most strong to the least strong; it means skill level $1$ is the strongest possible.

The integer $N$ will be divisible by $K$, and all contestants are going to have distinct levels of skill.

$1 \le K \le N \le 5000$ $1 \le v_i \le 10^9$

Output🔗

The first and only line of output must contain the minimal required number of minutes.

Sample Input 1🔗

4 1
9 12 5 13

Sample Output 1🔗

1

Sample Input 2🔗

6 3
7 9 8 3 6 5

Sample Output 2🔗

3

• Memory Limit: 256MB
• Time Limit: 2sec

Nima lives in a big enchanted forest where trees are very tall and grow really quickly (And sometimes talk!). That forest can be represented as an $N \times N$ matrix where each field contains exactly one tree. Nima is very fond of the trees in this forest. He spent years observing them and talking to them, and for each tree, he measured how much it grew in a year. The trees grow continuously. For example, if the tree grows 3 meters in a year, it will grow 1.5 meters in half a year.

Apart from trees, Nima likes mushrooms from the enchanted forest. Sometimes, he eats suspicious colorful mushrooms, starts talking to trees, and the trees ask him peculiar questions. Yesterday, this unfortunate thing happened and the trees asked what would be the size of the largest connected group of trees that have equal heights if the trees continue growing at the same speed they’re growing at that moment.

Nima quickly measured the current height of all the trees in the forest and asked you to answer his question.

Two trees are considered adjacent if their fields in the matrix share a common edge. Two trees are considered connected if there is a sequence of adjacent trees that leads from the first to the second. A group of trees is considered connected if every pair of trees in the group is connected.

Input🔗

The first line of input contains the integer N. Each of the following $N$ lines contains $N$ integers. The $i$-th line contains the integers $h_{i, j}$, the initial height of the tree located in the $i$-th row and $j$-th column.

After that, $N$ more lines follow, each containing $N$ integers. The $i$-th line contains the integers $v_{i,j}$, the growth speed of the tree located in the $i$-th row and $j$-th column.

$1 \le N \le 700$$1 \le v_{i, j}, h_{i, j} \le 10^6$

Warning: The size of the input is very large, so it is recommended to use fast input methods (For example, use BufferedReader instead of Scanner in Java, or use scanf instead of cin in C++, or use PyPy instead of Python).

Output🔗

The only line of output must contain a single integer - the answer of the problem.

Sample Input 1🔗

3
1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3

Sample Output 1🔗

7

Sample Input 2🔗

2
3 1
3 3
2 5
2 5

Sample Output 2🔗

3

• Memory Limit: 256MB
• Time Limit: 1sec

Sina and Nima are USVAJAK agents tracking the movements of an unnamed corrupt government official. Anonymous sources have informed them about his upcoming escape attempt. They now know he plans to use his diplomatic contacts to try and hitch a ride on a CIA jet leaving from Jabolgha airport.

It’s well-known that all CIA jets have the string FBI somewhere in their registration codes. They gathered a list of all jets scheduled for the designated day. There are exactly five jets on the list. Write a program that will find out all CIA jets.

Input🔗

There are exactly $5$ rows of input, each row representing exactly one jet registration code from the list. A registration code is a sequence of at most $10$ uppercase English letters, digits 0 to 9, or dashes -.

Output🔗

The only line of output must contain a list of integers, indicating the corresponding input rows containing registrations of CIA jets, sorted in increasing order.

If there are no CIA jets, output the string HE GOT AWAY!.

Note: Uppercase and Lowercase letters are considered different, so He Got Away! is wrong!

Sample Input 1🔗

A-FBI2
9A-IRKOK
RE-KGB3
I-NTERPOL
GM-MI6

Sample Output 1🔗

1

Sample Input 2🔗

N323-CIA
F5-B13I
F-BI-32
MPM-DU-CIA
HAKHFSHT

Sample Output 2🔗

HE GOT AWAY!

Sample Input 3🔗

45-FBI
BOND-007
DT-FBI14
S1N4-13
N1M4-FBILL

Sample Output 3🔗

1 3 5

• Memory Limit: 256MB
• Time Limit: 1sec

Sina decided to challenge Nima! He gave him a real number $A$ and a bag full of cards with exactly one number $1-5$ written on each card. There is an unlimited quantity of each type of card.

Nima's task is to pick the minimum number of cards in a way that the average of the numbers written on them equals exactly $A$.

Input🔗

First and only line of input contains real number $A$.

$A$ will have between $1$ and $9$ decimal places, inclusive . $1 \le A \le 5$

Output🔗

First and only line of output should contain 5 nonnegative integers - numbers of the ones, twos, threes, fours and fives used, respectively. If there are multiple solutions, output any one of them.

Sample Input 1🔗

5.0

Sample Output 1🔗

0 0 0 0 1

Sample Input 2🔗

4.5

Sample Output 2🔗

0 0 0 1 1

Sample Input 3🔗

3.20

Sample Output 3🔗

0 0 4 1 0

• Memory Limit: 256MB
• Time Limit: 1sec

Pari has set up a new parquet flooring for her room. Her room is $W$ meters wide and $L$ meters long.

The blocks are of quadratic shape and each has an area of one quadratic meter. Once Pari had set up the flooring, which consists of yellow-colored blocks, she decided to paint the blocks on the edge of the room black.

The picture above illustrates the floor from the test case #2 – outer blocks are black, while the remaining two inner blocks are yellow.

Mari has come to visit Pari. While Pari was serving her biscuits, she counted the number of blocks of each color. When Mary returned home, she recalled of the two numbers and wished to calculate the dimensions of Pari’s room. Help her!

Input🔗

The first and only line of input contains two integers separated by a space, $R$ (the number of black blocks) and $B$ (the number of yellow blocks).

$8 \le R \le 5000$ $1 \le B \le 2\ 000\ 000$

Output🔗

The first and only line of output must contain the dimensions of Pari's room, $L$ and $W$, respectively. If the numbers differ, output the bigger one first. The test data is designed to somehow ensure that a unique solution always exists.

Sample Input 1🔗

8 1

Sample Output 1🔗

3 3

Sample Input 2🔗

10 2

Sample Output 2🔗

4 3

Sample Input 3🔗

24 24

Sample Output 3🔗

8 6

• Memory Limit: 256MB
• Time Limit: 1sec

Pari and Mari’s favourite recreation is competing against each other in some mathematical games. This time they took a stack of $N$ cards and settled on the following rules:

1. Pari is the first to play, then Mari, then Pari again, then Mari and so on;
2. Pari can take any number of cards (between 1 and $N$, inclusive) from the stack during her first move;
3. In each of the following turns the current player must take at least $1$ card and is allowed to take at most double the amount of cards taken during the previous turn by the other player; naturally, she cannot take more cards than the remaining amount in the stack;
4. The player who takes the last card is the winner.
5. Both Pari and Mari play optimally (i.e. if it is possible for one player to beat the other, that player will always win). Pari can take all the $N$ cards in the first move and win the game, but this makes the game too boring. So she asked you to find the minimum number of cards that she must take during her first turn such that she is guaranteed to win the game.

Input🔗

The first and only line of input contains the positive integer $N$, the number of cards in the starting stack.

$1 \le N \le 10^{15}$

Output🔗

Print the required minimum number of cards that Pari needs to remove during her first turn.

Sample Input 1🔗

4

Sample Output 1🔗

1

Sample Input 2🔗

8

Sample Output 2🔗

8

• Memory Limit: 512MB
• Time Limit: 2sec

In a little town called Jabolgha, $N$ people are living. Each of them has borrowed some money from exactly one other inhabitant of Jabolgha. Now the time has come to pay back all the debts, but the only problem is that everybody has spent all of their money!

The mayor of Jabolgha has decided to solve this problem. The town will give money to a few people (by inviting them to a variant of Squid Game where they can all win some money) so that they can pay back their debts. When some people get their money back, a chain reaction is started - for example, person A gets money from the game. Person A uses that money to pay their debt toward person B. Person B then uses that money to pay the debt towards person C, etc. If person B didn’t have enough money to pay back the debt, they wait until they get enough. If they have more than enough money, person B will keep what is left after payback.

Another example: if two people live in Jabolgha, and they owe $200$ Chugh (Chugh is the currency of Jabolgha) to each other, the town will give $200$ Chugh to one of them so they can pay back the debt to the other one.

Note that people may earn different amounts of money from the game.

Your task is to calculate the minimum total amount of money the game has to give to some subset of the inhabitants so that after the payback protocol described above all debts are paid.

Input🔗

The first line of input contains one integer $N$, the number of inhabitants of Jabolgha. They are numbered from $1$ to $N$.

The following $N$ lines contain two integers, separated by space. In $i$-th of those lines, the first number - $A_i$ represents the id of the person $i$-th person owes money to, and second $B_i$ represents the amount of the debt in Chugh.

$2 \le N \le 200\ 000$ $1 \le A_i \le N, A_i \neq i$ $1 \le B_i \le 10\ 000$

Output🔗

Print a single integer - the minimum total amount of money the game in Jabolgha has to give to its inhabitant players so all debts are returned.

Sample Input 1🔗

4
2 50
1 50
4 30
3 30

Sample Output 1🔗

80

Sample Input 2🔗

3
2 120
3 40
2 80

Sample Output 2🔗

160

Sample Input 3🔗

5
3 30
3 20
4 90
5 40
3 60

Sample Output 3🔗

110

• Memory Limit: 256MB
• Time Limit: 1sec

Pari loves spiderman and how he hangs upside down from the ceiling, so she likes to rotate everything. Right now she is rotating tables of letters. She wrote an $R \times C$ table onto a piece of paper. She has also chosen an angle $K$, a multiple of $45$, and wants to rotate her table that many degrees clockwise.

It turns out this task is a bit too hard for Pari, so help her out.

Input🔗

The first line contains two integers $R$ and $C$, the number of rows and columns in Pari's table.

Each of the next $R$ lines contains one row of Pari's table, a string of $C$ lowercase letters. The last line contains an integer $K$, a multiple of $45$ between $0$ and $360$ (inclusive).

$1 \le R \le 10$ $1 \le C \le 10$

Output🔗

Output Pari's table rotated $K$ degrees clockwise. The output must contain the smallest number of rows and columns possible. Some rows may have some leading spaces, but extra leading or trailing space is now allowed.

Sample Input 1🔗

3 4
pari
sina
mari
45

Sample Output 1🔗

  p
 s a
m i r
 a n i
  r a
   i

Sample Input 2🔗

3 4
pari
sina
mari
90

Sample Output 2🔗

msp
aia
rnr
iai

Sample Input 3🔗

3 4
pari
sina
mari
315

Sample Output 3🔗

   i
  r a
 a n i
p i r
 s a
  m