Bomboslav works in a nice and beautiful office. All the office is decorated with stylish designer clocks. Their face is a standard circumference with 60 equidistant marks along it that stand for the minutes. 12 out of these 60 marks are bigger than the others (starting from the topmost, equidistant with a step of five marks), these marks stand for hours. The clocks are stylish because they have to digits written on them at all, as the author supposed everyone is familiar with their location and which mark correspond to which value.
Today, someone place this clock above the Bomboslav's workplace. He checked them several times and noticed, that their behavior is somehow strange. Taking a closer look he realized that he is actually looking in the mirror that reflects the clocks located behind him. This means that the face of the clocks is reflected along the vertical line that passes through the center of the clock face. Now he wants to be able to determine what is the current time, knowing the time in the mirror version of the clocks.
Clocks are made in such a way that both hand movement is discrete, i.e. the hour hand always points at one of 12 large marks, showing the current hour, while the minute hand always points at one of 60 marks, showing the current minute.
The only line of the input contains two integers h and m (0 ≤ h ≤ 11, 0 ≤ m ≤ 59) — the current position of hour hand and the current position of the minute hand in the reflected version of the clocks. h = 0 means that the hour hand points upward, h = 3 stands for the position pointing right, h = 6 — down, and h = 9 — to the left. The same is true for the minute hand and values m = 0, m = 15, m = 30 and m = 45.
Print two integers x and y (0 ≤ x ≤ 11, 0 ≤ y ≤ 59) — the actual time shown on the clocks.
2 45
10 15
6 0
6 0
The picture below illustrates the first sample. Left clocks show what Bomboslav sees, while right clocks stand for the original positions of the clock hands. Hour hand is red, while minute hand is blue.
Arkady is a huge fun of machine learning, he tries to apply it in every problem he works on. He believes in an ultimate magic power of this popular young part of computer science. That is why Arkady always invents new machine learning features to compute them for his favorite objects.
Let us recall that a string is called palindrome if it reads the same from the beginning to the end and vice versa, from the end to the beginning. For each string in his data base Arkady wants to compute its shortest substring that consists of at least two characters and is a palindrome. If there are several such string Arkday wants to pick lexicographical smallest one.
The only line of the input contains a single string from Arkady's data base, that is a non-empty sequence of lowercase English letters. The length of this string is at least 2 and doesn't exceed 200 000 characters.
Print the shortest substring of the input string that consists of at least two characters and is a palindrome. Do not forget that Arkady want to find lexicographical smallest possible such string.
abac
aba
yandex
-1
We say that string a = a1a2... an is lexicographical smaller than string b = b1b2... bm if one the following is true:
- if n < m and a1 = b1, a2 = b2, ..., an = bn, that is the first string is a prefix of the second string.
- there exists such position 1 ≤ i ≤ min(n, m), that a1 = b1, a2 = b2..., ai - 1 = bi - 1 and ai < bi, that is the first string has a smaller character at the first position where the string differ.
After a tough workday Olya and Tolya decided to visit a shooting range. They already heard induction training, got riffles in their hands and are now standing at shooting positions. Across them there is a wall with n targets located on it. Each target can be considered as a figure at the plane and is either a circle or a rectangle. Targets can overlap and intersect in any ways.
Before they start shooting, Olya and Tolya decided to draw a line that will split the plane with all targets in two parts in order to make it possible to identify shots. However, to make it fair they want this line to divide each of the targets in two equal parts. That is, for each circle and each rectangle, the line must divide this figure in two parts of equal area.
Olya and Tolya were arguing hard to come up with this division plan. However, they are not sure that such line even exists and ask you to check whether desired division is possible or not.
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of targets. Each of next n lines starts with an integer ti (0 ≤ ti ≤ 1) that define the type of this target. ti = 0 means that this target is a circle and three more integers ri, xi and yi follow (1 ≤ ri ≤ 1000, - 10 000 ≤ xi, yi ≤ 10 000). They define the radius and coordinates of the circle center respectively. If ti = 1, then this target is a rectangle and it is defined by eight more integers x1, i, y1, i, x2, i, y2, i, x3, i, y3, i, x4, i, y4, i — coordinates of its vertices listed in the order of clockwise or counter-clockwise traversal ( - 10 000 ≤ xj, i, yj, i ≤ 10 000). It is guaranteed that given four points form a rectangle of positive area.
If there exists a line that splits each of the targets in two parts of equal area, print "Yes" in the only line of the output. Otherwise, print "No".
Alexey is a very experienced interviewer. Though he had done several hundreds of internship interviews, he feels that it is time to change something. The candidates now easily solve all the wonderful tasks he was successfully using for all these years.
There is no choice, so Alexey came up with a new task. You are given a sequence of integers that on step one consists of two integers 1. On each step you insert a new element between any two neighboring elements of a sequence, and a value of a new element is equal to their sum. After several first steps the sequence looks like as follows:
- 1 1
- 1 2 1
- 1 3 2 3 1
- 1 4 3 5 2 5 3 4 1
During the interview Alexey plans to ask candidate to write a program that, being given an integer value n, will compute the number of time value n occurs in the sequence on step n. Though Alexey has no idea how to solve this problem, he heard that the next candidate is an experienced participant of programming competition, so he should be able to come up with a solution.
The input consists of a single integer n (1 ≤ n ≤ 1013).
Print one integer, the number of times integer n appears in the sequence on step n.
4
2
1
2
To ensure user data is safe and won't be loss in an accident Arkady always invents and tests new ways to organize backup. This time he enumerated all computers he possess from 1 to n and for each computer with index from 1 to n - 1 identified backup computer pi. He followed the rule that the index of backup computer should always be greater than the index of a computer itself, i.e. pi > i. Because of this rule there is no backup for computer n.
During the current experiment Arkady has chosen some configuration of values pi and now plans to turn computers off in some order, one computer every second. The experiment is over when computer with index n is turned off. Initially, each computer has a block of data of size 1. When computer x is turned off, its block of data of size 1 is copied to computer px. In case there were some other block at computer x (that were received as a backup from other computers) and they are not copied and are considered lost. Moreover, if computer px is already off, the block of data from computer x is not copied anywhere and is also considered lost.
Akrady wants his experiment to last as long as possible. However, he has to follow one more rule: if during some second the number of blocks of data that has gathered at some machine is equal to k, this machine must be turned off during next second to ensure hardware safety. Note, that the last second (when computer n is turned off) is not counted.
The first line of the input contains a single integer t (1 ≤ t ≤ 20) — the number of tests.
Then follow t individual tests descriptions. Each description starts with two integers n and k (1 ≤ n ≤ 100 000, 2 ≤ k ≤ 10) — the number of computers that take part in this experiment and the maximum possible load of one computer. Next line contains n - 1 integers p1, p2, ..., pn - 1 (i + 1 ≤ pi ≤ n).
For each of t tests print one integer equal to the maximum possible number of seconds before Arkady will have to turn off machine number n.
4
6 3
6 6 6 6 6
4 3
2 3 4
1 3
10 3
8 8 8 9 9 9 10 10 10
2
3
0
7
To test the most recent advances in algorithms of machine learning Evgeny uses n·m processors that are arranged in unit cells of n × m board. Thus, processors occupy n rows, each containing m of them. Two processors are called neighbors if they are arranged in neighboring cells of one row, or at the same positions in neighboring rows.
As a result of an unsuccessful experiment with a new algorithm some processors learned to lie to Evgeny. However, thanks to the base version of algorithm that was used, all the processors that learned to lie, do so every time they report something to Evgeny, so the result of their work is still ease to interpret.
Now Evgeny is working to determine which of the processors always say lie, but to start with he wants to understand the possible size of the problem. To make this he asked each of the processors whether it is true that among its neighbors there are processors that work correct and processor that always return lie? To his surprise, each of the processors answered positive. Now Evgeny wonders, what is the minimum possible number of lying processors on the board that can result such answers?
The only line of the input contains two integers n and m (1 ≤ n ≤ 7, 1 ≤ m ≤ 100) — the number of rows on the board and the number of processors in each of the rows respectively.
Print one integer — the minimum possible number of liars among the processors on the board, that could result that each of the processors reported that among its neighbors there are both correct and lying processors.
2 3
2
6 6
10
One of the possible solutions in the first sample is (liars are marked as 1's): 1):
100
001