Oh, those math lessons! Today, for example was the fourth test on the subject. To those who finished ahead of time the teacher offered an extra task for bonus points.
Two n-digit numbers are written on the blackboard, first composed of only the digit d1, second — of only the digit d2. Determine which digit occupies position k in the sum of those numbers. Positions are numbered left to right starting from 1.
You want bonus points, don't you?
Input format
Four lines of input contain four integers: n, d1, d2 and k. It is guaranteed that k is correct.
Output format
Output a single decimal digit — answer to the problem.
Constraints
1 ≤ n ≤ 109
1 ≤ k ≤ n + 1
1 ≤ d1, d2 ≤ 9
Notes on sample
Sample has n = 2 (adding two-digit numbers), d1 = 5 (first number is 55), d2 = 8 (second number is 88). Sum is 55 + 88 = 143. k = 1 (teacher asks the first digit of the result). The digit at first position of the number 143 is 1.
Fantasy chess is a variant of chess composition. Puzzles of this variant contain changes to some of the accepted rules of the game or utilize unusual pieces or boards.
Amazon is a fantasy chess piece which can move as either a queen or a knight. It is usually represented on diagrams as a horse with the crown. You can see all possible moves of this piece on a picture below. Amazon is so strong and independent that it can checkmate the enemy king without the help of another friendly piece.
White amazon and black king are positioned on a normal chess board. Determine whether the king is checkmated.
Input format
First line of input contains two integers separated by space: x1 and y1 — coordinates of the white amazon. Second line contains coordinates of the black king x2 and y2 in the same format. Piece positions are guaranteed to be different.
Output format
Output Yes or No — answer to the problem's question.
Constraints
1 ≤ x1, x2, y1, y2 ≤ 8
Notes on the samples
See the picture. In the second sample the king can capture the amazon.
Children theme park has opened a new attraction "Karousel" for n persons. According to safety regulations, when the attraction is running, children must be seated so that the center of mass of all riders coincides with the center of carousel and the distances between them alongside the circumference is equal. For example, for n = 6, 2, 3 or 6 children may ride simultaneously, while for n = 5 — only exactly 5. In other words, attraction is allowed to start if it has k children, where k — is a divisor of n and k ≠ 1.
There are d children waiting in the queue for the carousel. After finishing the ride children leave to other attractions. What is the minimum number of runs to let all children ride the carousel once each?
Input format
Two lines of input contain integers n and d.
Output format
Output a single integer — answer to the problem. If it is impossible for all children to get a ride, output -1.
Constraints
1 ≤ (d, n) ≤ 105
Notes on sample
In the first sample n = 16 and d = 14 (16 seats on carousel, 14 children in the queue). It is enough to run carousel 3 times: first time for 8 children, second — for 4, third — for 2.
In the first sample n = 15 and d = 7. It is impossible to let all children ride since according to regulations only 3, 5 or 15 are allowed to ride at a time.
Marina Tsvetaeva, Andrej Belyj and Sasha Chernyj are spending the evening playing chess.
For each game two of them are playing and the third person is waiting to take the place of the loser.
The winner of each game plays next game with white pieces.
After playing n games silver age poets were surprised to find out
that white side had been repeatedly winning k times in a row, followed by a black victory every time.
Andrej Belyj likes to play with white pieces, Sasha Chernyj — with black, Marina Tsvetaeva likes either of the colors. Determine the number of games where both players played with the color they like. First game was between Andrej Belyj (played with white) and Sasha Chernyj (played with black). No game was a draw.
Input format
Two lines of input contain two integers n and k.
Output format
Output a single integer — problem answer.
Constraints
1 ≤ n ≤ 109
1 ≤ k ≤ 100
Notes on sample
4 games were played. White player had been winning one game, and then losing the next one.
In the first game Belyj — Chernyj both play the color they like. Andrej wins, playing with white.
In the second game Belyj — Tsvetaeva both play the color they like. Andrej loses, playing with white.
In the third game Tsvetaeva — Chernyj both play the color they like. Marina wins, playing with white.
In the final game Tsvetaeva — Belyj only Marina plays the color she likes. So the answer is 3 games.
The city of N has a happy event! On the single street of the city, new street lamp will be installed and the new pharmacy will open. Help the city governor to find optimal places for these objects.
The street is represented by a segment of coordinate axis, where the leftmost house has coordinate 0. Let's assume house sizes to be negligibly small compared to the street length and represent houses as points on the axis.
The lamp has "brightness" parameter expressing the largest distance from the lamp where the light reaches. For example when brightness is equal to 10, lamp installed at the point x = 25 will light the street on the segment from 15 to 35 inclusive.
The pharmacy has "remoteness" parameter expressing the largest distance from it to the house such that people from that house will still visit. For example when remoteness is equal to 100, pharmacy located at point x = 25, will be visited by people living in houses with coordinates from 0 to 125 inclusive (there are no houses with negative coordinates).
Input format
First line of input contains three integers separated by spaces: n — number of houses, a — brightness и b — remoteness. Next n lines contain two space-separated integers each: xi, qi — coordinate of the house and number of people living in it (houses may be empty).
Output format
Output two integers — maximum number of houses illuminated by the lamp and maximum number of people who will visit the pharmacy. Both lamp and pharmacy may be located between the houses as well as at points with the coordinate of some house.
Constraints
1 ≤ n, a, b ≤ 105
0 ≤ xi, qi ≤ 109
Notes on sample
Sample contains five houses, lamp brightness 15 and pharmacy remoteness 20. Lamp can be installed at either point 15, or point 25, in both cases 4 houses will be illuminated. Pharmacy may be located at point 20, in which case all city inhabitants will be able to visit.
Zhenya Slavin is a first human born on Mars. He is yet a little boy and likes to look at the digital clock hanging opposite of his bed. Most of all he likes the moments when all digits on the clock become identical. In those moments he always claps joyfully.
Since the period of rotation of Mars around its axis is different from that of the Earth,
Martian colonists decided that:
a single Martian day will be exactly h Martian hours;
a single Martian hour will be exactly m Martian minutes;
a single Martian day minute be exactly s Martian seconds.
Current time on Mars is hM hours, mM minutes and sM seconds. After how many seconds will Zhenya clap? Time on the Martian digital clocks is displayed with leading zeroes in all positions. Extra positions are not used.
Input format
Input contains six integers, one per line: h, m and s — description of Martian day subdivision, followed by hM, mM and sM — current time.
Output format
Output a single integer — number of seconds until the moment when all digits on the clock become identical.
Constraints
0 ≤ hM < h ≤ 106
0 ≤ mM < m ≤ 106
0 ≤ sM < s ≤ 106
Notes on samples
It the first sample Martian days are no different from Earth ones (24 hours of 60 minutes of 60 seconds). Now it is 23 hours 50 minutes exactly (clock displays digits 23:50:00). After 10 minutes (or 600 seconds) the clock will display zeroes in all positions.
It the second sample Martian days contain 627 hours of 5 minutes of 777 seconds. Now it is 49 hours 3 minutes and 2 seconds (clock displays digits 049:3:002). After 61 hours 3 minutes and 109 seconds (or 239425 Martian seconds) the clock will display ones in all positions.
Утенок Даки заинтерисовался последовательностями.
Немного изучив данную тему, Даки решил ввести свою характеристику для
последовательностей из целых чисел, под названием d-харктеристика.
Для вычисления d-характеристики требуется определить всех чисел последовательности.
Если таких элементов в последовательности нет, то d-харктеристика равна 0.
Например, если дана последовательность − 1532, то значение будет .
Формат входных данных
Дана последовательность из N целых чисел a1, a2, …, aN
Первая строка входных данных содержит целое число N.
Вторая строка содержит N целых чисел ai, разделённых пробелами.
Формат выходных данных
Выходные данные должны содержать единственное целое число — значение d-характеристики.
Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).
Формат входного файла
Первая строка входного файла содержит целое число n - размер массива.
Во второй строке содержится строке n целых чисел ai - сам массив.
В третьей строке указано число m — количество перемещений.
В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.
Формат выходного файла
В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.
