2017 USP Try-outs
A. Comunicating the Tibet
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The Himalayas form the highest mountain range in the world (with mountains as high as 7,200 meters). Located in Asia, this mountain system has parts in the Bhutan, China, India, Nepal, and Pakistan. In China, the Tibet is a region delimited by the Himalayas.

The Tibet, which is the highest region on Earth, is an autonomous region inside the People's Republic of China. In this region there are Buddhist temples with Tibetan monks, which are visited every year by many people from the whole world. To facilitate communication, the Central Tibetan Administration (ACT, in Portuguese) wishes to install some radio-frequency antennas around the Tibet. The ACT considered the N most important temples where they wish to install these antennas. The World Communication Association (ACM, in Portuguese) was hired to setup and configure these antennas at the temples. ACM charged their star engineer Mashiro "thunderstorm" Sanae with this job.

After reading about the history and customs of Tibetan monks, Mashiro found a curious fact: the Tibetans have a particular fixation for the number K. By studying the map with the location of the N temples, Mashiro noticed that if he walks through distinct temples until he returns to the starting one, the number of temples he goes through (including the first) never has the form mK + 1 for any nonnegative integer m. He was fascinated with his discovery, and realized the importance of the number K for Tibetans. Mashiro knows that, when setting up the antennas, neighboring temples should receive distinct frequencies to avoid interference. Having this constraint in mind and knowing the importance of the number K for the Tibetans, Mashiro wishes to find an assignment of frequencies to antennas that uses at most K distinct frequencies, or determine that this assignment is impossible.

Mashiro had an idea to solve this problem and has already started coding it. Can you beat him to it?

Input

The first line has three integers, N, M, and K, the number of temples, the number of paths that join neighboring temples and the special number revered by the Tibetan people, respectively. The temples are represented by numbers from 1 to N.

The next M lines contain two distinct integers each. Each pair of integers represents two neighboring temples. No two lines among these M lines contain the same pair of integers.

  • 1 ≤ N ≤ 5·104
  • 0 ≤ M ≤ 5·105
  • 1 ≤ K ≤ N
  • 1 ≤ fi ≤ K
Output

If there is no possible frequency assignment to the temples, print a line containing "-1" (without the double quotes). Otherwise, print N lines. The i-th line must contain a single integer, fi, the frequency assigned to temple i, where 1 ≤ fi ≤ K. If there is more than one solution, any one will do.

Examples
Input
4 0 1
Output
1
1
1
1
Input
3 3 3
1 2
2 3
1 3
Output
1
2
3
Input
3 2 1
1 2
2 3
Output
-1

B. Building a Bianzhong
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The Bianzhong is one of the most distinctive musical instruments of ancient Chinese culture. It is made of bronze bells hanging from a wooden frame, and they are struck by a mallet. The Bianzhong, along with other instruments, was an important part of many Chinese rituals from yore.

The Bianzhong bells (or zhong bells) have two distinguishing characteristics when compared to regular bells. The mouth is elliptic (rather than circular), which allows the bell to produce two different musical tones (represented by the characters ' + ' and ' - '), depending on where it is struck. Its use at concerts has been getting more and more common.

The company IME (Esoteric Musical Instruments, in Portuguese) acquired at an auction a set of N zhong bells of distinct sizes. Now they want to build a Bianzhong from these bells. But the bells purchased have the following oddity: the i-th bell has a sound power of value i, for i = 1, 2, ..., N. The wooden frame for the bells was already built. The final step to complete the Bianzhong is to determine for each bell which of the musical tones it should play.

IME would like to have a Bianzhong with a balanced configuration, that is, the total sound power of bells with musical tone ' + ' should equal the total sound power of bells with musical tone ' - '. The total sound power of a set of bells is the sum of the sound powers of the bells in the set. IME would like to count on your help to find a balanced solution, and thus complete setting up its Bianzhong.

Input

The input has a single integer N, the number of bells acquired by IME.

  • 1 ≤ N ≤ 106
Output

If it is not possible to find a balanced bell configuration, print "-1" (without the double quotes). Otherwise, the output should have a line with N characters s1, ..., sN, where si is the musical tone of the i-th bell (' + ' or ' - '). If more than one configuration is possible, print any one of them.

Examples
Input
4
Output
-++-
Input
5
Output
-1

C. Coprimes
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A. Tuttu (a distant relative of W. Tutte) is a young mathematician with a promising future. As a child, he was very lonely, since he had no siblings nor cousins. One of his earliest Christmas gifts was a Number Theory book. That is the reason he focused on studying this area since a very early age. He was very interested in coprimes, but he could not solve the following problem and he asked you to help him.

Given a sequence of N positive integers, we want to answer M queries. Each query is represented by two indices. He would like to know if there exists a pair of relatively prime numbers in the sequence whose positions are between the given indices.

Input

The first line has the numbers N and M separated by a space. The second line contains N positive integers a1, a2, ..., aN separated by a space. Then there are M lines, each one containing two integers, and r, separated by a space, encoding a query.

  • 2 ≤ N ≤ 5·104
  • 1 ≤ M ≤ 2·105
  • 1 ≤ ai ≤ 5·105, 1 ≤ i ≤ N
Output

For each one of the queries you should print "S" (without the double quotes) if there is a pair of relatively prime integers between (including) the sequence positions indexed by and r, or "N" otherwise.

Examples
Input
5 3
6 15 10 6 7
1 3
2 4
4 5
Output
N
N
S
Input
6 4
39 78 143 26 22 70
2 5
3 6
4 6
1 5
Output
N
S
N
S
Note

Two numbers are called coprime (or relatively prime) if their greatest common divisor is the number 1.

D. Geographic Information System
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Geographic Information Systems (SIGs, in Portuguese) are becoming more and more important and useful in our lives. These systems are used in countries' national defense systems, for the analysis of public health data, in archaeology, and even in climate studies. In China, these systems are changing the way companies analyze and plan their business strategies. This development comes together with a bigger investment in R&D related to such technology. For this reason, the Chinese Association of Geographic Information Systems (ACSIG, in Portuguese) wants to attract students to work on projects related to this technology.

ACSIG knows that, in 2018, the brightest young minds in the planet will travel to Beijing to compete in the ACM ICPC World Finals. Given this event's reputation, ACSIG wants to recruit some of these contestants to be part of future projects. Now they are planning the problems they will use in their recruiting process. One of these problems is as follows.

Given the map of a certain geographic region and the subdivision of this region into sub-regions, we want to find a rectangle that contains in its interior all the points that define the subdivision. Now let's define the problem more formally. Consider that the map is the usual Cartesian plane, and the subdivision is given by a set of N straight lines. We want to find the rectangle with axis-aligned sides with the smallest area, and which contains all the vertices of the subdivision (the intersection points of the set of lines). Consider that the points in the boundary of the rectangle are also part of its interior.

ACSIG would like to test your knowledge, and asked you to solve this problem.

Input

The first line contains an integer, N, the number of straight lines that define the subdivision. The i-th of the next N lines contains two real numbers, mi, and bi. These numbers represent the straight line mix - bi. It is guaranteed that at least one pair of these lines intersect.

  • 1 ≤ N ≤ 105
  • 0 < |mi| ≤ 107
  • 0 ≤ |bi| ≤ 107
Output

Print a line containing four real numbers , where are the coordinates of the bottom left vertex of the rectangle and (xr, yr) are the coordinates of the top right vertex. Absolute or relative errors of up to 10 - 4 are accepted.

Examples
Input
2
0.444444 -9.0000
-0.125 -11.0000
Output
3.51220 10.56098 3.51220 10.56098
Input
5
-0.4444 -9.0000
-0.1250 -11.0000
0.5000 -7.0000
-0.5000 -2.0000
-0.2000 -5.0000
Output
-125.89928 1.72668 16.36661 64.94964
Input
6
3 5
3 9
3 15
3 19
-2 3
-2 -6
Output
0.40000 -9.40000 5.00000 1.60000

E. Teamwork
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Teamwork is highly valued in the ACM ICPC. Since the beginning, the ICPC has distinguished itself from other programming contests in that teamwork is a key factor.

The University of Beijing, host of next year's World Finals, is planning recreational activities for the participants. They want to prepare games that show the importance of teamwork and enable new acquaintances among the contestants from all over the world. One of the staff members has been thinking about the following game.

In a court we have several N-person teams. The goal of each team is roughly as follows: starting from a corner, each team must take all of its members to the other corner of the court. The winning team is the one that finishes this in the shortest time.

Now we explain the game more formally. Consider the team that starts at corner A and must take all of its members to corner B. The following procedure is repeated:

  1. While there are team members at corner A,
    • If there is only one team member, he is the only one that goes to corner B.
    • Otherwise, two team members must tie one leg of each with a rope and go to B.
  2. Once arriving at B, they untie their legs, if applicable.
  3. If there are still team members at corner A, some team member at B must return to A with the rope.

The organization wants to form the teams so that no team has an advantage. They entrusted you with the following task. Given the time in seconds that the members of a team take to go from a corner to the other, find the minimum time it takes for the team to take all its members from corner A to corner B. When two team members cross the court with their legs tied, the time for the pair to cross is the maximum between the times of the two members.

Input

The first line of input contains an integer N, the number of team members. The next line contains N integers ti, the time in seconds that the i-th team member takes to go from one corner to the other.

  • 1 ≤ N ≤ 105
  • 1 ≤ ti ≤ 109
Output

Print a single integer, the minimum time required for the whole team to reach corner B.

Examples
Input
3
30 40 50
Output
120
Input
4
10 20 50 100
Output
170
Note

In the first example, the process can be completed in 120 seconds as follows:

  1. The first and second members go from A to B in 40 seconds.
  2. The first member returns to corner A in 30 seconds.
  3. The first and third team members go from A to B in 50 seconds.

This is not the only way to complete the process in this total time, but no other way does it in strictly less than 120 seconds.

F. Hitting the target
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Sitting in front of the computer for too long is no good for your health. Keeping this in mind, the MaratonIME coaches decided to motivate the contestants to practice sports, not just programming. They didn't want to stick with the basics, so they chose the bow and arrow.

However, they noticed that too many people showed up at practice sessions just to shoot arrows. To discourage people with no interest in programming, they decided to add a requirement for shooting arrows: one would have to code a program that takes the coordinates of 3 arrows and record the final score. The target is made of ten concentric circles of proportional radii, that is, the smallest circle has radius R, the second one has radius 2R, the third one has radius 3R, and so on. The circle with smallest radius grants 10 points, and the largest one awards only 1 point. An arrow that hits the boundary between two circles grants the largest of the two scores.

Don't miss your opportunity to participate at the programming contest: write this program.

Input

The input has a line that has an integer R, the radius of the smallest circle. Next there are three lines with pairs of integers, x and y, the points in the target hit by each arrow. The target center is at coordinate (0, 0).

  • 1 ≤ R ≤ 102
  •  - 103 ≤ x, y ≤ 103
Output

The output has a single integer: the final score.

Examples
Input
1
0 0
0 1
0 0
Output
30
Input
2
0 0
0 2
0 3
Output
29

G. Splitting the Empire
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Carlitos "Curious" Nunes is studying the history of China at school. More specifically, he is studying the times known as the "Golden Age" of China. The History exam is soon to come and he decided to write some notes to help his studies. He wrote:

The Golden Age (600–1,600AD) is a period of history when China was ruled by the Tang (618–906AD) and Song (960–1,279AD) dynasties. It is characterized by the end of internal wars and by enormous commercial and technological development (tea, explosives, the compass, and printing).

Growth in commerce took place during the rule of the Song dynasty. To stimulate the exchange of goods among cities, Emperor Taizu Song built many roads joining the cities of the empire. On the one hand, one could reach any city from any other city using these roads. On the other hand, there were so many roads that people believed the following to hold: for any four cities, say A, B, C, and D,

d(A, B) + d(C, D)  ≤  max{d(A, C) + d(B, D),  d(A, D) + d(B, C)}, 

where d(U, V) is the smallest number of roads needed to go from U to V.

The Golden Age ended when the Mongols invaded China in 1,279AD and established the Yuan dynasty.

Genghis Khan, fearing a Chinese uprising, split the cities of the empire among his army commanders. The split up was performed so that each commander was responsible for a subset of cities such that no two of these cities was joined by a road. Furthermore, each city belonged to precisely one commander.

Carlitos is very curious to find how Genghis Khan could have made such a split, and how many commanders his army should have so that the split was possible. Carlitos wants to solve this puzzle before leaving for his vacation at Foz de Iguaçu. Can you help him?

Input

The first line has two integers, N and M, the number of cities and roads in the Chinese empire, respectively. The M lines that follow each contain two integers, u and v, the cities joined by one road. There are no two roads joining the same pair of cities.

  • 1 ≤ N ≤ 5·104
  • 2 ≤ M ≤ 5·105
  • 1 ≤ u, v ≤ N, u ≠ v
Output

Print an integer, the minimum number of commanders required to split up the empire.

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

H. Programming a robot
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The last edition of the world robot conference took place in China last year, the most recent innovations on robots were on display. Those ranged from machines able to make people's portraits to robots that can play soccer.

We want to program a robot, but a less sophisticated one. It takes only two commands:

  • Walk(k): takes k steps forward
  • TurnRight(): turns 90 degrees to its right.

At first, we just want to program this robot's movements. For that, we need you to print a sequence of commands to complete the following action: given the Cartesian coordinates of start and destination, and the initial direction the robot initially points to (North, South, East, or West), print a sequence of commands that takes the robot from its starting position to its destination.

Since we are always concerned about efficiency, we wish the sequence to be as small as possible.

Input

The input has one line with a pair of integers that indicate the starting coordinates, xo and yo, followed by a character that indicates a direction (N for North, S for South, E for East, or O for West). The next line contains a pair of integers indicating the destination coordinates, xd and yd.

  • 0 ≤ xo, yo ≤ 5·105
  • 0 ≤ xd, yd ≤ 5·105
Output

In the first line, print the smallest size of a sequence of commands that take the robot from start to destination. In the next lines, print one of these sequences, one command per line. For the command Walk((k)), print "A k" (without the double quotes). For the command TurnRight(), print "D".

If there is more than one sequence of instructions that work, any one of them will be accepted.

Examples
Input
15 2 E
7 9
Output
5
D
D
A 8
D
A 7
Input
0 0 N
0 12
Output
1
A 12

I. Protecting the Great Wall
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

China has a very rich history, with written records since 1,500BC. One of the cities that contributes a lot to this history is the capital city of Peking. It is visited yearly by many tourists seeking to get to places such as the Temple of Heaven, the Lugou Bridge, the Yinshan Pagoda Forest, or the Forbidden City. One of the most imposing tourist attractions is the Great Wall, for its history and sheer size.

Peking will host the ACM ICPC World Finals 2018, and one of the chosen group activities is to visit the Great Wall. The event organizers in China want to make these one of the best World Finals ever. They have been planning activities with great care for the safety of all participants throughout the city. For this reason, they charged Marcel "the optimizer" Saito with the job of securing the visit to the Great Wall.

The organizers can hire agents from N security teams, numbered from 1 to N. They may hire any number of agents (possibly none) from each team. The organizers assigned each of these teams a security value, that is, each agent in the i-th team adds Bi points to the security score. Marcel's goal is to come up with a hiring plan for agents so as to maximize the total security score, which is the sum of the security values of the hired agents.

On the other hand, the organizers informed Marcel that each group has its special workflow which may cause conflicts. For this reason, the hiring plan must satisfy a set of M constraints. The j-th constraint is defined by three integers Lj, Rj, and Cj, with the following meaning: the sum of the number of agents hired from the teams from Lj to Rj must be no more than Cj.

Now Marcel has all the data to find an optimal hiring plan and keep his reputable epithet. This looks like an interesting problem, so we want you to solve it as well.

Input

The first line contains two integers, N and M. The second line has N integers, B1, B2, ..., BN, where Bi is the security value of the agents in the i-th group. The next M lines contain information about each one of the constraints. The j-th of these M lines contains three integers, Lj, Rj, and Cj. Consider that each team appears in at least one of the M constraints.

  • 1 ≤ N ≤ 200.
  • 1 ≤ M ≤ 4000.
  • 0 ≤ Bi ≤ 2000.
  • 1 ≤ Lj ≤ Rj ≤ N.
  • 0 ≤ Cj ≤ 106.
Output

Print an integer, the total security score of an optimal hiring plan.

Examples
Input
4 5
5 12 10 6
2 4 1
1 4 1
3 4 1
1 1 1
1 2 1
Output
12
Input
2 1
12 4
1 2 2
Output
24

J. Deciphering Oracles
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

China is considered a forefather of math in Asia. Chinese mathematicians developed the binary system, and they had notions of algebra, trigonometry, and geometry. The most ancient records of Chinese math go back to the Shang dynasty (1,600-1,050 BC). Mathematicians at that time recorded their findings in animal bones and turtle plastrons. These texts were known as "Oracle Bones".

The office of the Investigators of Extraordinary Mysteries (IME, in Portuguese) is located in Anyang, capital of the Shang dynasty, and they have with them one of these oracles. The challenge to decipher this oracle was accepted by Marcio "the Indispensable" Himura. Marcio found that the oracle refers to a decimal system a bit different than the one we use. Working out on deciphering the oracle, he found that:

  1. The only numbers that are considered are integers from 1 to N.
  2. Given two distinct number x = a1a2... an and y = b1b2... bm, we consider x < y if
    • , or if
    • and x < y (according to the decimal number system).

Marcio was surprised by the last part of the oracle. He concluded that the Chinese had an algorithm that, given a number K, finds the position of K in the number system. Besides, they know how to find the number that occupies position K. Unfortunately, the investigators at IME have not yet found the oracles where such algorithms are described.

Marcio is very curious to know how this can be done. He knows you wish to qualify for the ACM ICPC World Finals next year, and so he challenged you to solve this problem.

Input

The input has two integers, N and K.

  • 1 ≤ N < 1018
  • 1 ≤ K ≤ N
Output

The output has two integers separated by a space. The first integer is the position of K in the number system. The second is the number that occurs at position K.

Examples
Input
10 2
Output
3 10
Input
100 5
Output
16 11

K. Cutting Strings
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice, Beto, and Carlos are playing with twine. Alice starts by pulling taut the string of twine, then she folds it and holds the string at the fold. Beto holds the loose ends on the other side. They then repeat the following procedure. Carlos cuts the string with scissors, thus separating Alice and Beto. Alice, without letting go of the strings she was holding, grabs the loose ends of the strings held by Beto and he does the same to the loose ends of the strings held by Alice.

How many separate strings will they have after the procedure is repeated K times?

Input

The input has a single integer, K.

  • 0 ≤ K ≤ 30
Output

The output has a single integer, the amount of separate strings at the end of the process.

Examples
Input
0
Output
1
Input
1
Output
3

L. Approximate Search
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Baidu, Inc. is a Chinese Web services company. Among the services they provide are web search and "Baidu Baike", a virtual, collaborative encyclopedia. Due to its remarkable growth and interesting set of challenges its employees need to solve on a daily basis, many young programmers aspire to get a internships or even full-time jobs at this company.

Emi "the Retired" Shouko will travel to Beijing next year and would like to get an interview there for an internship. He is now reading some books with common coding interview questions. He is especially interested in problems related to web search. One of the problems that has been drawing Emi's attention is as follows.

Given an N-character text and an M-character pattern, we would like to know if it is possible to find the pattern in the text. However, the pattern does not need to occur exactly. The search allows a maximum of K mismatches, where a mismatch can be any of the following: a substitution, an insertion, or the removal of a character.

Emi really liked this problem. He has had an idea and started coding his solution furiously. He knows you would love to join him for his trip to Beijing, so he wishes you to solve this problem as well.

Input

The first row of the input has the integers M, N, and K. The second row contains a pattern made of M characters from 'a' to 'z'. The third row contains a text made of N characters from 'a' to 'z'.

  • 1 ≤ M ≤ 102
  • 1 ≤ N ≤ 106
  • 1 ≤ K ≤ 20
Output

If the pattern occurs in the text with at most K mismatches, print "S" (without the double quotes). Otherwise, print "N" (without the double quotes).

Examples
Input
3 6 2
aed
abcdef
Output
S
Input
3 6 1
aed
abcdef
Output
N
Note

In the first example, if we remove the character 'b' and replace 'c' with 'e', the resulting text will be "aedef", which contains the pattern "aed". The same cannot be said if the maximum numbers of allowed mismatches were 1.