CPG Training Contest - 1
A. LLPS
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

This problem's actual name, "Lexicographically Largest Palindromic Subsequence" is too long to fit into the page headline.

You are given string s consisting of lowercase English letters only. Find its lexicographically largest palindromic subsequence.

We'll call a non-empty string s[p1p2... pk] = sp1sp2... spk (1  ≤  p1 < p2 < ... < pk  ≤  |s|) a subsequence of string s = s1s2... s|s|, where |s| is the length of string s. For example, strings "abcb", "b" and "abacaba" are subsequences of string "abacaba".

String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y| if either |x| > |y| and x1 = y1, x2 = y2, ..., x|y| = y|y|, or there exists such number r (r < |x|, r < |y|) that x1 = y1, x2 = y2, ..., xr = yr and xr  +  1 > yr  +  1. Characters in the strings are compared according to their ASCII codes. For example, string "ranger" is lexicographically larger than string "racecar" and string "poster" is lexicographically larger than string "post".

String s = s1s2... s|s| is a palindrome if it matches string rev(s) = s|s|s|s| - 1... s1. In other words, a string is a palindrome if it reads the same way from left to right and from right to left. For example, palindromic strings are "racecar", "refer" and "z".

Input

The only input line contains a non-empty string s consisting of lowercase English letters only. Its length does not exceed 10.

Output

Print the lexicographically largest palindromic subsequence of string s.

Examples
Input
radar
Output
rr
Input
bowwowwow
Output
wwwww
Input
codeforces
Output
s
Input
mississipp
Output
ssss
Note

Among all distinct subsequences of string "radar" the following ones are palindromes: "a", "d", "r", "aa", "rr", "ada", "rar", "rdr", "raar" and "radar". The lexicographically largest of them is "rr".

B. Let's Watch Football
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Valeric and Valerko missed the last Euro football game, so they decided to watch the game's key moments on the Net. They want to start watching as soon as possible but the connection speed is too low. If they turn on the video right now, it will "hang up" as the size of data to watch per second will be more than the size of downloaded data per second.

The guys want to watch the whole video without any pauses, so they have to wait some integer number of seconds for a part of the video to download. After this number of seconds passes, they can start watching. Waiting for the whole video to download isn't necessary as the video can download after the guys started to watch.

Let's suppose that video's length is c seconds and Valeric and Valerko wait t seconds before the watching. Then for any moment of time t0, t ≤ t0 ≤ c + t, the following condition must fulfill: the size of data received in t0 seconds is not less than the size of data needed to watch t0 - t seconds of the video.

Of course, the guys want to wait as little as possible, so your task is to find the minimum integer number of seconds to wait before turning the video on. The guys must watch the video without pauses.

Input

The first line contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 1000, a > b). The first number (a) denotes the size of data needed to watch one second of the video. The second number (b) denotes the size of data Valeric and Valerko can download from the Net per second. The third number (c) denotes the video's length in seconds.

Output

Print a single number — the minimum integer number of seconds that Valeric and Valerko must wait to watch football without pauses.

Examples
Input
4 1 1
Output
3
Input
10 3 2
Output
5
Input
13 12 1
Output
1
Note

In the first sample video's length is 1 second and it is necessary 4 units of data for watching 1 second of video, so guys should download 4 · 1 = 4 units of data to watch the whole video. The most optimal way is to wait 3 seconds till 3 units of data will be downloaded and then start watching. While guys will be watching video 1 second, one unit of data will be downloaded and Valerik and Valerko will have 4 units of data by the end of watching. Also every moment till the end of video guys will have more data then necessary for watching.

In the second sample guys need 2 · 10 = 20 units of data, so they have to wait 5 seconds and after that they will have 20 units before the second second ends. However, if guys wait 4 seconds, they will be able to watch first second of video without pauses, but they will download 18 units of data by the end of second second and it is less then necessary.

C. Card Constructions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A card pyramid of height $$$1$$$ is constructed by resting two cards against each other. For $$$h \gt 1$$$, a card pyramid of height $$$h$$$ is constructed by placing a card pyramid of height $$$h-1$$$ onto a base. A base consists of $$$h$$$ pyramids of height $$$1$$$, and $$$h-1$$$ cards on top. For example, card pyramids of heights $$$1$$$, $$$2$$$, and $$$3$$$ look as follows:

You start with $$$n$$$ cards and build the tallest pyramid that you can. If there are some cards remaining, you build the tallest pyramid possible with the remaining cards. You repeat this process until it is impossible to build another pyramid. In the end, how many pyramids will you have constructed?

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$) — the number of test cases. Next $$$t$$$ lines contain descriptions of test cases.

Each test case contains a single integer $$$n$$$ ($$$1\le n\le 10^9$$$) — the number of cards.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^9$$$.

Output

For each test case output a single integer — the number of pyramids you will have constructed in the end.

Example
Input
5
3
14
15
24
1
Output
1
2
1
3
0
Note

In the first test, you construct a pyramid of height $$$1$$$ with $$$2$$$ cards. There is $$$1$$$ card remaining, which is not enough to build a pyramid.

In the second test, you build two pyramids, each of height $$$2$$$, with no cards remaining.

In the third test, you build one pyramid of height $$$3$$$, with no cards remaining.

In the fourth test, you build one pyramid of height $$$3$$$ with $$$9$$$ cards remaining. Then you build a pyramid of height $$$2$$$ with $$$2$$$ cards remaining. Then you build a final pyramid of height $$$1$$$ with no cards remaining.

In the fifth test, one card is not enough to build any pyramids.

D. Chat Order
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Polycarp is a big lover of killing time in social networks. A page with a chatlist in his favourite network is made so that when a message is sent to some friend, his friend's chat rises to the very top of the page. The relative order of the other chats doesn't change. If there was no chat with this friend before, then a new chat is simply inserted to the top of the list.

Assuming that the chat list is initially empty, given the sequence of Polycaprus' messages make a list of chats after all of his messages are processed. Assume that no friend wrote any message to Polycarpus.

Input

The first line contains integer n (1 ≤ n ≤ 200 000) — the number of Polycarpus' messages. Next n lines enlist the message recipients in the order in which the messages were sent. The name of each participant is a non-empty sequence of lowercase English letters of length at most 10.

Output

Print all the recipients to who Polycarp talked to in the order of chats with them, from top to bottom.

Examples
Input
4
alex
ivan
roman
ivan
Output
ivan
roman
alex
Input
8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina
Output
alina
maria
ekaterina
darya
Note

In the first test case Polycarpus first writes to friend by name "alex", and the list looks as follows:

  1. alex

Then Polycarpus writes to friend by name "ivan" and the list looks as follows:

  1. ivan
  2. alex

Polycarpus writes the third message to friend by name "roman" and the list looks as follows:

  1. roman
  2. ivan
  3. alex

Polycarpus writes the fourth message to friend by name "ivan", to who he has already sent a message, so the list of chats changes as follows:

  1. ivan
  2. roman
  3. alex

E. Recursive Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let us define two functions f and g on positive integer numbers.

You need to process Q queries. In each query, you will be given three integers l, r and k. You need to print the number of integers x between l and r inclusive, such that g(x) = k.

Input

The first line of the input contains an integer Q (1 ≤ Q ≤ 2 × 105) representing the number of queries.

Q lines follow, each of which contains 3 integers l, r and k (1 ≤ l ≤ r ≤ 106, 1 ≤ k ≤ 9).

Output

For each query, print a single line containing the answer for that query.

Examples
Input
4
22 73 9
45 64 6
47 55 7
2 62 4
Output
1
4
0
8
Input
4
82 94 6
56 67 4
28 59 9
39 74 4
Output
3
1
1
5
Note

In the first example:

  • g(33) = 9 as g(33) = g(3 × 3) = g(9) = 9
  • g(47) = g(48) = g(60) = g(61) = 6
  • There are no such integers between 47 and 55.
  • g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4

F. k-Amazing Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ integers numbered from $$$1$$$ to $$$n$$$.

Let's define the $$$k$$$-amazing number of the array as the minimum number that occurs in all of the subsegments of the array having length $$$k$$$ (recall that a subsegment of $$$a$$$ of length $$$k$$$ is a contiguous part of $$$a$$$ containing exactly $$$k$$$ elements). If there is no integer occuring in all subsegments of length $$$k$$$ for some value of $$$k$$$, then the $$$k$$$-amazing number is $$$-1$$$.

For each $$$k$$$ from $$$1$$$ to $$$n$$$ calculate the $$$k$$$-amazing number of the array $$$a$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of elements in the array. The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case print $$$n$$$ integers, where the $$$i$$$-th integer is equal to the $$$i$$$-amazing number of the array.

Example
Input
3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1
Output
-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1