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 no 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.

Input format

The only line of the input contains two integers $h$ and $m$ $(0\le h\le 11\text{, }0\le m\le 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\text{, }m=15\text{, }m=30\text{and }m=45$

Output format

Print two integers $x$ and $y$ $(0\le x\le 11\text{, }0\le y\le 59)$ — the actual time shown on the clocks.

Sample 1

Sample 2

Notes

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.

Solution

Consider the movement of "real" and "reflected" hands. If "real" hands rotates for some angle, "reflected" hand passes exactly the same angle in other direction. Thus, the sum of angles of two hands is always equal $360$ degrees. For each hand we will find its resulting position independently. For hour hand it is $12$ minus the current position, while for minute hand it is $60$ minus current position. In both cases we should not forget to replace $12$ or $60$ with $0$.

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.

Input format

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 $\mathrm{200\; 000}$ characters.

Output format

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.

Sample 1

Sample 2

Notes

We say that string $a=a_1{a}_2\text{ ... }{a}_n)$ is lexicographical smaller than string $b=b_1{b}_2\text{ ... }{b}_m)$ if one the following is true:

• if $n<m\text{ and }{a}_1=b_1\text{, }{a}_2=b_2\text{, }\text{ ..., }{a}_{\mathrm{n}}=b_{\mathrm{n}}\text{, }$ that is the first string is a prefix of the second string.
• there exists such position $1\le i\le min(n\text{,}m)\text{, that }{a}_1=b_1\text{, }{a}_2=b_2\text{ ..., }{a}_{i-1}=b_{i-1}\text{ and }{a}_{\mathrm{i}}=b_{\mathrm{i}}\text{, }$ that is the first string has a smaller character at the first position where the string differ.

Solution

Consider some substring of the given string that is a palindrome. We can remove its first character and its last character and the string will remain a palindrome. Continue this process till the string length becomes two or three (depending on parity).

The number of substrings of length two or three is linear, same as their total length. Thus, we can apply naive algorithm to select optimum palindrome. If there is no palinromic substring of length two or three, print $-1$.

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.

Input format

The first line of the input contains a single integer $n(1\le n\le \mathrm{100\; 000})$ the number of targets. Each of next $n$ lines starts with an integer $t_i(0\le t_i\le 1)\text{, }$ that define the type of this target. $t_i=0\text{, }$ means that this target is a circle and three more integers $r_i\text{, }{x}_i\text{ and }{y}_i\text{, }$ follow $(1\le r_i\le 1000\text{, }-10\; 000\le x_i\text{, }{y}_i\le 10\; 000)$ . They define the radius and coordinates of the circle center respectively. If $t_i=1\text{, }$ then this target is a rectangle and it is defined by eight more integers $x_{1\text{,}i}\text{, }{y}_{1\text{,}i}\text{, }{x}_{2\text{,}i}\text{, }{y}_{2\text{,}i}\text{, }{x}_{3\text{,}i}\text{, }{y}_{3\text{,}i}\text{, }{x}_{4\text{,}i}\text{, }{y}_{4\text{,}i}$ — coordinates of its vertices listed in the order of clockwise or counter-clockwise traversal $(\mathrm{-10\; 000}\le x_{j\text{,}i}\text{, }{y}_{j\text{,}i}\le \mathrm{10\; 000})\text{. }$ It is guaranteed that given four points form a rectangle of positive area.

Output format

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”.

Sample 1

Sample 2

Sample 3

Solution

To solve this problem we will use a simple geometry fact that a line split a circle in two parts of equal area if and only if this line passes through the circle center. Similarly, a line splits a rectangle in two parts of equal area if and only if it passes through the intersection point of its diagonals. In both cases, sufficiency follows from point symmetry and necessity can be shown by considering a line that passes through the center and is parallel to a given one.

Now we only need to check whether there exists a line that contains all the centers. For the sake of simplicity we will work with doubled coordinates to keep them integer. This allows us to get the center of the rectangle by computing the sum of coordinates of two opposite vertices.

If there are no more than two distinct points among the set of all center, the answer is definitely positive. Otherwise, consider any pair of distinct points and check that each center belongs to the line they define. To check whether three points $a\text{, }b\text{ and }c(a\ne b)$ belong to one line we can compute the cross product of vectors $b-a$ and $c-a\text{. }$ Overall complexity of this solution is $O(n)\text{. }$

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.

Input format

The input consists of a single integer $n(1\le n\le {10}^{13})\text{. }$

Output format

Print one integer, the number of times integer $n$ appears in the sequence on step $n$.

Sample 1

Sample 2

Solution

We would like to start with some lemmas.

Lemma 1. Any two neighboring integers are co-prime at any step.

Use math induction. Base case is trivial as 1 and 1 are co-prime. Consider the statement is correct for first $n$ steps. Then, any integer produced during step $n+1$ is a sum of two co-prime integers. However, $gcd(a+b\text{, }b)=gcd(a\text{, }b)\text{, }$ thus, any two neighbors are still co-prime.

Lemma 2. Each ordered pair of integers $(a\text{, }b)$ appears as neighbors exactly once (and at one step only).

Proof by contradiction. Let $k$ be the first step such that some ordered pair appeared for the second time. Denote this pair as $(p\text{, }q)$ and $i\le k$ is the step of another appearance o this pair. Without loss of generality let $p>q$ , then $p$ was obtained as a sum of $p-q$ and $q$, thus during the steps $i-1$ and $k-1$ there was also a repetition of some pair, that produces a contradiction.

Lemma 3. Any ordered pair of co-prime integers will occur at some step.

Let $p$ and $q$ be neighbors at some step. Then, if $p>q$ it was obtained as a sum of $p-q$ and $q$, so they were neighbors on the previous step. Two steps behind we had either $p-2q$ and $q$, or $p-q$ and $2q-p$ (depending on which is greater, $p-q$ or $q$) and so one.The process is similar to Euclid algorithm and continues while we don't have $1$ and $x$. Finally, pairs $(1\text{, }x)$ and $(x\text{, }1)$ always appear at step $x$$. Moving along the actions in backward direction we conclude that any of the intermediate pairs should appear during the process, thus, pair $(p\text{, }q)$ also appears.

Compute Euler function is a well-studied problem. This know this is a multiplicative function, so $n=p_1^{k_1}·p_2^{k_2}·\text{ ... }·p_n^{k_n}$ , the number of co-prime integers is $(p_1^{k_1}-p_1^{k_1-1})·(p_2^{k_2}-p_2^{k_2-1})·\text{ ... }(p_n^{k_n}-p_n^{k_n-1})$ Factorization of $n$ can be done in $O(\sqrt{n})$ time.

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 $p_i$ He followed the rule that the index of backup computer should always be greater than the index of a computer itself, i.e. $p_i>i$ . Because of this rule there is no backup for computer $n$.

During the current experiment Arkady has chosen some configuration of values $p_i$ , 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$, turned off, its block of data of size $1$ copied to computer $p_x$ . 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 $p_x$ 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.

Input format

The first line of the input contains a single integer $t(1\le t\le 20)$ — the number of tests.

Then follow $t$ individual tests descriptions. Each description starts with two integers $n$ and $k$ $(1\le n\le \mathrm{100\; 000}\text{, }2\le k\le 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 $p_1\text{, }{p}_2\text{, ... }{p}_{\mathrm{n}-1}(i+1\le p_i\le n)$ .

Output format

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$.

Sample

Solution

In this problem we are given a rooted tree. At one step, one node is removed. If the node is being removed and its immediate ancestor is still present, the value in this ancestor is increased by $1$ (initially all values are equal to $1$). If the value of some node is equal to $k$, it should be removed at the next step. The goal is to maximize the number of step when root is removed.

Notice, that if the root has only $k-1$ descendant we can remove the whole tree before touching the node $n$. Otherwise, descendants should be split in three sets: totally removed subtrees, subtrees with their root remaining, and one subtree, whose root is removed at the end causing the node $n$. to be removed as well. Run depth-first search to compute the following value of dynamic programming:

$a(v)$ is the number of nodes we can remove in subtree of $v$ if we are allowed to remove $v$ at any point. One can show that $a(v)$ equals the total number of nodes in the subtree.

$b(v)$ is the number of nodes we can remove in subtree of $v$ if we are not allowed to touch node $v$. If there are less than $k-1$ descendants, $b(v)$ is equal to $a(v)-1$ . Otherwise, we should pick $k-2$ descendant to use value $a(u)$ , while for other we use $b(u)$ . This $k-2$ descendants are selected by maximum value of $a(u)-b(u)$ .

$c(v)$ equal to the number of nodes we can remove if we are allowed to remove node $v$ but this should be done at the very end. Value of $c(n)$ is the final answer. We have to select some $k-2$ descendants to use $a(u)$ , one to use $c(u)$ and for others we take $b(u)$ . Try every descendant as a candidate for $c(u)$ and for other use greedy algorithm to pick best $a(u)-b(u)$ . Precompute the sorted array of all descendants and compute the sum of $k-2$ best. If descendant $x$ to be used with $c(x)$ is among these $k-2$ use the $k-1$ (there should be at least $k-1$ descendants, otherwise we destroy the whole subtree).

The overall complexity is $O(n\text{ log }n)$

To test the most recent advances in algorithms of machine learning Evgeny uses $n·m$ processors that are arranged in unit cells of $n\times 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?

Input format

The only line of the input contains two integers $n$ and $m$ $(1\le n\le 7\text{, }1\le m\le 100)$ — the number of rows on the board and the number of processors in each of the rows respectively.

Output format

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.

Sample 1

Sample 2

Notes

One of the possible solutions in the first sample is (liars are marked as 1’s): 1):
100
001

Solution

We are going to use the fact that $n\le 7$ and compute profile dynamic programming. If we already filled first $i$ columns of the table and everything is correct for first $i-1$ columns, we only need to know the state of last to columns in order to be able to continue.

Let $dp(i\text{, }m1\text{, }m2)$ , where $i$ varies from $1$ to $m$, $m1$ and $m2$ are bitmasks in range from $0$ to $2^n-1$ mean the minimum number of processors required to fill first $i$ columns in order to make first $i-1$ columns correct and last two columns be filled as $m1$ and $m2$ respectively. The number of different states is $O(m·2^{2n})$ . Finally, to compute the relaxations we try all possible masks $m3$ for the new state $dp(i+1\text{, }m2\text{, }m3)$ .

Applying bit operations and some precomputations we obtain $O(m·2^{3n})$ running time. We can speed it up a lot by precomputing all valid $m3$ for a pair of $(m1\text{, }m2)$ .

Exercise: come up with $O(nm{2}^{2n})$ solution.