Simulation tasks

ID 32947. Watch

ID 38138. Year of the Cow

The Chinese calendar is known to follow a 12-year cycle: Ox(Ox), Tiger(Tiger), Rabbit(Rabbit), Dragon(Dragon), Snake(Snake), Horse(Horse), Goat(Goat) , Monkey(Monkey), Rooster(Rooster), Dog(Dog), Pig(Pig), Rat(Rat), and then Ox again. 
For many years, Besi the cow has been proud that she was born in the year of the Ox. Her friend Elsa wants to know how many years her birth is from Besie's and hopes you can help her find it out based on the relationship between the birth dates of some of the cows on the farm.

"Mildred born in previous Dragon year from Bessie",

or

"Mildred born in next Dragon year from Bessie" (previous - previous, next-next).

The last word is the name of the cow, which is either Bessie or the cow previously mentioned in the previous input line.
The first word is the name of a cow that is not Bessie and has not yet been mentioned in the input. All cow names have a maximum of 10 characters a..z or A..Z.

The 5th word is one of the zodiac signs mentioned earlier.

4th word or "previous" or "next". For example, the phrase "Mildred born in previous Dragon year from Bessie", means that the year of birth of Mildred was the year of the Dragon (Dragon), the closest and strictly earlier (not equal) to the year of Bessie's birth.

Examples

ID 38195. Checkout

At one of the Moscow railway stations tickets are sold by N cash desks. Each cash desk works without interruption for a certain period of time according to a fixed schedule (the same every day). It is required to determine how long during the day all cash desks work at the same time.

Input
First, a single integer N (0 < N ≤ 1000) is entered.

Each of the next N lines contains 4 space-separated integers, the first two of which indicate the opening time of the cash desk in hours and minutes (hours — integer from 0 to 23, minutes — integer from 0 to 59), the remaining two &mdash ; closing time in the same format. Numbers are separated by spaces.

The opening time means that at the corresponding minute the cash desk is already working, and the closing time — that at the appropriate moment the cashier is no longer working. For example, a cash desk open from 10:30 a.m. until 18:30, 480 minutes daily.

If the opening time coincides with the closing time, then the cash desk is open around the clock. If the first time is greater than the second, then the cash desk starts work before midnight, and ends — the next day.

Imprint
It is required to print one number — the total time per day (in minutes), during which all N cash desks work.

Examples

ID 38320. End of K-th lesson

At school, the duration of each lesson is 45 minutes, and the breaks between lessons – just 5 minutes. The first lesson starts at 8 am sharp. Write a program that answers the question "What time does the Kth lesson end at this school?"

Input
One natural number K is entered, not exceeding 15.

Imprint
Print the end time of the Kth lesson: first hours, then minutes, separating them with a space.

Examples

ID 38321. Placement of laptops

The school decided to put two rectangular laptops on one rectangular table. Laptops should be placed so that their sides are parallel to the sides of the table. Determine what dimensions the table should have so that both laptops fit on it and the table area is minimal.

Input
Four natural numbers are entered, the first two specify the dimensions of one laptop, and the next two — the dimensions of the second. Numbers do not exceed 1000.

Imprint
Print two numbers — table dimensions. If multiple answers are possible, print any of them (but only one).

Note
The examples show all kinds of answers to the given problem. Your program should output one of them.

Examples

ID 38322. Cards

Vasya made cards by writing the first N capital letters of the Latin alphabet on them. Vasya put the cards in a pile.

Then he takes the first card from the top and puts it in a new pile. Then he puts the second card at the bottom of this new pile, the third — on top of a new pile, then the fourth — down again, next — up, etc.

After that, it turned out that the cards are strictly alphabetical, if you look at them from top to bottom.

Write a program to print the order in which the cards were in the original pile.

Input
A natural number N is entered (N does not exceed 26).

Imprint
Print the letters written on the cards in the original pile, if viewed from top to bottom (capital latin letters should be printed without spaces between them).
 

Examples

ID 38324. herringbone

"Draw" using the characters on the forest screen. In this case, do not use commands to move the cursor around the screen. Your program must print the characters of the lines (or the entire line) sequentially.

Forest — it is one or more Christmas trees. Each Christmas tree is characterized by the number of triangles in it and the size of the smallest triangle. The herringbone consists of triangles whose vertices are strictly under each other, and each next triangle contains one line more than the previous one.

All Christmas trees should start vertically from the first line. Each Christmas tree should be located as far to the left as possible, while the Christmas trees should not touch (i.e. there should not be symbols depicting another Christmas tree near the symbols of the Christmas tree on the right, left, bottom, top, and also diagonally) and the order should not be violated Christmas trees.

Christmas trees should be depicted with the symbols «#» (lattice), and the empty spaces between them — symbols «.» (dot). All lines must display the same number of characters, and there must be a line in which the last character is a pound sign, the last line must contain hacks (i.e., a rectangle of dots and bars should be displayed, it should not contain extra columns and rows).

Input
The number of Christmas trees is entered N, and then N pairs of natural numbers describing the Christmas trees: the first number of each pair specifies the number of triangles in the Christmas tree, and the second — the size of the smallest triangle. The Christmas trees are described in order from left to right (if you look at the tops of the Christmas trees).

It is guaranteed that the input data will be such that the number of characters to be output in one line will not exceed 79.

Imprint
Output the required "drawing". See examples for better understanding.
 

Examples

...#......#....
..###....###...
...#....#####..
..###.....#....
.#####...###...
...#....#####..
..###..#######.
.#####....#....
#######..###...
........#####..
......#######.
......#########

#.#...#...
..#..###..
.###..#...
.....###..
....#####.
......#...
.....###..
....#####.
...#######

ID 38335. Seating arrangements

N participants came to the Olympiad in Informatics. It is known in which schools the participants of the Olympiad study. There are N computers in the computer class, lined up along the wall. You need to seat the participants of the Olympiad so that no two participants from the same school sit next to each other.

Input
The program receives as input a positive integer number of participants in the Olympiad N1000. Next, N lines contain the numbers of schools where the participants of the Olympiad study. School numbers — integers from 1 to 3000.

Imprint
The program should output N numbers — the numbers of the schools of the participants of the Olympiad in the order in which they need to be seated in the computer class. The output sequence of school numbers must be a permutation of the given school numbers. The displayed answer should not contain two identical school numbers in a row.

If the problem has no solution, you need to print a single number 0.

Numbers can be displayed both in separate lines and in one line separated by a space. If there are several seating options, then you need to display any of them (but only one).

Examples

ID 38352. Estimate passenger traffic

The bus route passes through N stops (including the final ones). The Passenger Flow Research Department recorded data on how many people got off and how many boarded the bus at each stop. Write a program that will use this data to determine the maximum number of people on this bus at the same time.

Input
The input file contains the number N (2≤N≤100) – number of stops along the route. Next, the number of people who got on the bus at the end is set. Next comes (N-2) pairs of numbers that specify for intermediate stops the number of exits and the number of incoming passengers. Finally, there is a number that specifies the number of people who got off the bus at the final stop.

The number of boarding passengers at each stop did not exceed 100. The data is correct, in particular, the total number of passengers boarding the bus at all stops is always equal to the total number of boarding passengers.

Imprint
In the output file print a single integer — the maximum number of people who at some point simultaneously rode the bus.
 

Examples

ID 38359. Black and white palindromes

Given a strip of checkered paper with a length of N cells and a width of 1 cell, in which some cells are painted black, and the rest — into white. Such a stripe is called a palindrome if the sequence of black and white cells when viewed from left to right is the same as when viewed from right to left.

You are given a strip of length N. You need to cut it into strips that are palindromes so that the number of resulting strips is strictly less than (2/5)N + 3.

Input
The first line of the input file contains the number N — the length of the original strip (N — a natural number not exceeding 100000). Next comes N numbers describing the coloring of the strip: 0 means a black cell, and 1 — white.

Imprint
In the output file print in ascending order the numbers of the cells of the original strip, after which you need to make cuts.
 

Examples

ID 38360. Beam of light in the dark realm

The Dark Kingdom is an NxM labyrinth, some cells of which are surrounded by mirror walls, and the rest — empty. The entire labyrinth is also surrounded by a wall of mirrors. In one of the empty cells of the labyrinth, a traffic light was placed that emits rays in 4 directions: at 45 degrees relative to the walls of the labyrinth. It is required to depict the trajectory of these rays.

When the beam comes to the corner through which the mirror walls pass, it goes further as shown in the pictures (the cells that are surrounded by mirror walls are shown in gray). The ray behaves in a similar way when it comes to the border of the maze.


Input
The first line of the input file contains two natural numbers N and M — the number of rows and columns in the maze (each of the numbers is not less than 1 and not more than 100). The next N lines contain exactly M characters in each — labyrinth map. The symbol * (asterisk) denotes a cell surrounded by mirrored walls, . (dot) — empty cell, symbol X (capital Latin letter X) — the cell in which the traffic light is located (there is exactly one such cell).

Imprint
In the output file print N lines with M characters in each — image of a labyrinth with trajectories of rays. Here, as before, * (asterisk) should denote cells surrounded by mirrored walls, . (dot) — empty cells through which light rays do not pass, / (slash) — cells through which the beam of light passes from the lower left corner to the upper right (or back — from the upper right to the lower left), \ (backslash) — the cells through which the ray passes from the upper left corner to the lower right (or vice versa), and the symbol X (capital Latin letter X) — cells through which rays pass along both diagonals.

Examples

3 5
X....
.....
.....

XXXXX
XXXXX
XXXXX

3 3
...
..X
...

/X\
X.X
\X/

ID 38476. Collider

Physicists are conducting an experiment to study particles of three types: x, y and z. They launch a numbered row of n particles into the collider. During the experiment, one specific particle is affected, after which the particle disappears from the i-th place of the row and instantly appears at the place j. After it disappears, the numbers of particles to the right decrease by 1, and after the appearance, the numbers of particles to the right increase by 1. After a certain number of impacts, physicists are interested in which particle is in place k. Write a program to help physicists.

Input
The first line of the file contains two integers: n – number of particles and m — total number of exposures and questions (1 ≤ n ≤ 1000000, 1 ≤ m ≤ 15000). On the second line — a sequence of characters x, y and z of length n. Each of the next m lines (1 ≤ m ≤ 15000) describes an impact or question. The line, which describes the impact, begins with the character a and after the space two integers from the interval [1; n]. The first of them shows the initial, and the second  - the final location of the particle during the impact. The line in which the question is described begins with the symbol q and after a space one integer from the interval [1; n]. It indicates the position that physicists are interested in.

Imprint
Output as many lines as there are questions in the input file. In line number i you need to write the answer to the question i — the name of the corresponding particle x, y or z.

Explanations for example
The sequence after the first exposure – xxyyzxxzxzyyzyx, the sequence after the second exposure – xxyxyzxxzxzyyzy, sequence after the third exposure –
 

Examples

ID 38573. Robots

There are N halls in the dungeon connected by tunnels. In some halls there are robots that have simultaneously received a command to gather in one place.

The robots are arranged in such a way that, having received a command, they all begin to move at such a speed that the tunnel between any two halls is overcome in 1 minute. Robots cannot stop (including in the halls) and also change direction while in the tunnels (however, once in the hall, the robot can go out of it through the same tunnel through which it came to this hall).

Write a program that calculates the minimum time it takes for all the robots to get together (in a hall or in a tunnel).

Input
First, the numbers N — number of halls (1≤N≤400) and K — number of tunnels (1≤K≤20000). Next, K pairs of numbers are introduced, each pair describes the numbers of halls connected by a tunnel (you can move along the tunnel in both directions). There may be several tunnels between two halls. The tunnel can connect the hall to itself. This is followed by the number M (1≤M≤400) — the number of robots. Then M numbers are entered, specifying the numbers of the halls where the robots are located at the beginning. There can be several robots in one room.

Imprint
Print the minimum time in minutes after which the robots can get together. If the robots can never get together, print a single number –1 (minus one).

Examples

ID 38576. "Sorting" with candy

An array of N different natural numbers from 1 to N is given. works as follows. First, the first and second elements are compared, and if the first is greater than the second, then they are swapped. Then the same procedure is carried out with the second and third element, …, with the penultimate and last. Then this procedure is repeated again with the first and second, with the second and third, …, with the penultimate and last elements. And so (N & ndash; 1) times.

Sorting "with candy" is performed according to the same rules, but additionally given a list of pairs of numbers that do not change with each other under any conditions (in this case, the sorter gets a candy for missing the corresponding exchange). For example, the presence of a pair (4,1) in the list means that if at some point the numbers 4 and 1 or 1 and 4 are nearby, and according to the sorting algorithm they need to be swapped, then the exchange will not happen, and the sorter will get candy .

It is required to sort "with candy" given array and return the sort result.

Input
First enter the number N — the number of numbers in the array, then N numbers — array elements. Next, the number M — the number of pairs of numbers for which they give a candy, and then M pairs of numbers. If there is a pair (i,j) in the list, then the pair (j,i) also gets candy.

1≤ N≤ 5000.0≤ M≤ 10000.

Imprint
It is required to display the array after sorting.

Examples

ID 38596. drunk game

In the game of drunkard, the deck of cards is dealt equally to two players. Next, they reveal one top card at a time, and the one whose card is higher takes both of the revealed cards for himself, which are placed under the bottom of his deck. The one who remains without cards – loses.

For simplicity, we will assume that all cards are different in face value, and also that the lowest card defeats the highest card (“six takes ace”).

The player who takes the cards for himself first places the card of the first player under the bottom of his deck, then the card of the second player (that is, the card of the second player is at the bottom of the deck).

Write a program that simulates a game of drunkard and determines who wins. The game involves 10 cards with values ​​from 0 to 9, the big card beats the smaller one, the card with a value of 0 beats the card 9.

Input
The program receives two lines as input: the first line contains 5 numbers separated by spaces — card numbers of the first player, the second – similarly 5 cards of the second player. Cards are listed from top to bottom, meaning each line starts with the card that will be revealed first.

Imprint
The program should determine who wins the given hand, and output the word first or second, and then print the number of moves made before winning. If the game does not end within 10⁶ moves, the program should output the word botva.

Examples

ID 38849. Switching between windows

When a user is on the Windows operating system, they often have multiple applications running. Each of the applications runs in a separate window. To switch between windows, use the Alt+Tab key combination. This combination makes the active window the user was working in before switching to the currently active window.

To switch to another window, you can press the "Alt" key; and then, without releasing it, press the "Tab" key several times. To understand which window will become active after that, we will use the following model. Let n applications be running. Applications in the operating system are organized as a list and ordered in descending order of last activity time. That is, the application whose window is currently active – the first in the list, the application whose window was active before this – second, etc.

If you press the "Alt" key and then, without releasing it, press the "Tab" key k times, then the application window that is at (k mod n) + 1st place in the list will become active. Here a mod b means the remainder of dividing a by b. In other words, the operating system treats the list as cyclic, moving from the last element of the list to the first.

When a new application is launched, it is added to the top of the list.

A sequence of user actions is specified, where each action – either launching an application or switching between windows. Print a  list of application names in the order the user has accessed them.

Input
The first line contains an integer n – number of user actions ( 1 ≤ n ≤ 1000). The next n lines contain a description of the user's actions.

The launch of an application is described by the string "Run . Here "<application name"> – a string of no more than 100 Latin letters, numbers and spaces. It is separated from the word "Run"; exactly one space. All application names are different. Large and small letters are considered different.

Switching between applications is described by the string "Alt+Tab+...+Tab", here the substring "+Tab" repeated exactly as many times as the number of times the user pressed the Tab key without releasing the Alt key. This number does not exceed 100.

The first command in the input – always "Run" command.

Imprint
Print  n lines – the sequence of application names that the user was working with in the order in which their windows became active.
 

Examples

ID 38875. Spiral

The robot moves along the checkered plane and draws a spiral. Initially, it is in cell (0, 0) and is directed towards increasing the first coordinate.
Then it acts according to the following algorithm: it makes d moves forward, then it turns left and again makes d moves forward. After that, it turns  to the left and multiplies the value of d by k. The robot then repeats the described process. The robot stops after a total of exactly n moves.
It is required to display a picture showing the cells visited by the robot.

Input
The input is integers n, d and k (1 ≤ n ≤ 1000, 1 ≤ d ≤ 100, 2 ≤ k ≤ 5).

Imprint
Let the minimum rectangle of cells containing all the cells visited by the robot have height h and width w. On the first line print the numbers h and w separated by a space. The next h lines should contain w characters each, print "*" for the cell visited by the robot and "." for the unvisited.

Examples

5 5
*****
*...*
*.***
*....
**...

ID 39388. Contact tracing

Farmer John continues to take care of the health of his cows, consecutively numbered 1…N.
Recently, the FD checked them all and found out that some of them are sick. Using video from the barn, the FD can find out which pairs of cows interacted to spread the disease. The FD has collected a list indicating the time at which the interaction of pairs of cows in the video (t,x,y) took place, meaning that at time t cow x interacted with cow y. The FD also knows the following:

1.  Exactly one cow was initially infected (patient zero).
2.  Once a cow is infected, she passes the infection on to her next K interactions (possibly involving the same partner multiple times). After K times of transmission, she stops transmitting the infection (on realizing that she is infecting, she begins to thoroughly wash her hooves).
3.  Once she gets sick, she stays sick.

Examples

ID 39515. three four five cow change

The N  cows (1 ≤ N ≤ 100) of Farmer John are lined up. The i-th cow on the left has label i, for all 1≤i≤N.
The FD ordered the cows to repeat exactly K (1 ≤ K ≤10⁹) times the following two-step process:

The sequence of cows at positions A1…A2 on the left reverses their order (1≤A₁<A₂≤N).
Then the sequence of cows at positions B1…B2 on the left reverses their order (1≤B₁<B₂≤N).
Output the resulting order of cows for all i 1 ≤ i≤ N after running this process exactly K times.


Input
The first line contains N and K. The second line contains A₁ and A₂, the third line contains B₁ and B_{2.
Imprint
On the i-th line print the label of the i-th cow on the left after the process of all exchanges is completed.}

Examples

7 2
25
3 7

1
2
4
3
5
7
6

ID 28323. Trapped in the Haybales