Description

Given a string A and n strings B1, B2, B3, …, Bn, count the number of occurrences of string A in each of B1, B2, B3, … , and print the maximum number of occurrences. All of the strings contain only digits.

For example, if A is “50” , n = 3, and the n strings are

“5005”

“055050”

“55000”

then your answer should be 2 because A appears in “5005”  one time,  in “055050” two times, and in “55000” one  time. So the maximum number of occurrences is 2.

Note that if A is “99” and B1 is “9999”, the number of occurrences of A in B1 is counted as 3.

You may assume string B1 is always longer than string A.

Input

The first line of the input is the string A (0<length of A<=4). The second line is n (1<n<10) .

For the next n lines, each line contains a string Bi (length of A < length of Bi <9) and a ‘\n’ at the end of the line.

Output

The maximum number of occurrences of A appears in B1, B2, …, Bn. Note that you DO NOT need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The input contains three numbers, which are the 2nd, the 3rd and the 4th number of  an arithmetic progression (等差數列) or a geometric progression (等比數列). Your task is to distinguish which progression it is from this numbers and print out the first number and the 5th number.

For example, if the input is  3 5 7, then you know this is an arithmetic progression and the common difference is 2. So the 1st and 5th number is 1 and 9 respectively.

There are NO progression like 1 1 1 or 2 2 2 which are both an arithmetic progression and a geometric progression.

Input

Three integers

Output

The 1st and the 5th number of the progression. The two numbers should be separated by a blank.

You DO NOT need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given some integers, please list them in increasing order.

Input

First line is an integer T (T <= 20) followed by T test cases.

Each test case consists of two lines. First line is an integer n (n <= 10⁴), and second line contains n integers V₁, V₂, ..., V_n. (-2³¹< V_i < 2³¹-1 for 1 <= i <= n )

Output

For each test case, list a line of numbers from the smallest one to the largest one ending with '\n'. Two adjacent numbers in one line should be separated by a whitespace.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Source : ACM International Collegiate Programming Contest Asia Regional Contest, Tsukuba, 2016/10/16 

You are given an ordered sequence of integers, (1,2,3,...,n). Then, a number of requests will be given. Each request specifes an integer in the sequence. You need to move the specied integer to the head of the sequence, leaving the order of the rest untouched. Your task is to find the order of the elements in the sequence after following all the requests successively.

Sample Output Explanation : In Sample Input 1, the initial sequence is (1; 2; 3; 4; 5). The first request is to move the integer 4 to the head, that is, to change the sequence to (4; 1; 2; 3; 5). The next request to move the integer 2 to the head makes the sequence (2; 4; 1; 3; 5). Finally, 5 is moved to the head, resulting in (5; 2; 4; 1; 3).

Input

The input consists of a single test case of the following form.

n m

e₁

:

e_m

The integer n is the length of the sequence ( 1 <= n <= 200000 ). The integer m is the number of requests ( 1 <= m <= 100000 ). The following m lines are the requests, namely e₁,...,e_m, one per line. Each request e_i ( 1 <= i <= m ) is an integer between 1 and n, inclusive, designating the element to move. Note that, the integers designate the integers themselves to move, not their positions in the sequence.

Output

Output the sequence after processing all the requests. Its elements are to be output, one per line, in the order in the sequence.

There should be a new line at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Princess Twilight Sparkle's birthday is around the corner. As a good friend of Twilight, the best party pony Pinkie Pie decides to throw a birthday party for her! Pinkie plans to invite n  ponies to join this big party. At the beginning of the party, Pinkie will give away a bunch of balloons, and here's how it will work :

First, all ​ ponies, labelled from 1 to n, will sit in a circle. Pinkie will then give away three different colors of balloons -- red, blue and yellow. For each color, Pinkie will randomly choose a number x​. Counting begins at the pony labelled 1 and proceeds around the circle. After skipping x​ ponies, Pinkie will give that pony a balloon. The whole round stops when any pony could get two same balloons, and Pinkie won't give that pony the same balloon again. That is, there are three round of giveaway in total, and each pony will get three different colors of balloons at most.

For example, if there are 6 ponies in the party:

The first time Pinkie choose x = 2 and gives red balloons, so ponies labelled 2, 4 and 6 will get red balloons.

The second time Pinkie choose x = 3 and gives blue balloons, so ponies labelled 3 and 6 will get blue balloons.

The last time Pinkie choose x = 5 and gives yellow balloons, so all ponies will get yellow balloons.

(The order of getting the yellow balloons is : 5, 4, 3, 2, 1, 6)

Pinkie is wondering how many ponies will get three different kinds of balloons, so she can prepare for the following game she wants to play in the party. If you can help Pinkie, maybe she will teach you how to make a mouth-watering cupcake.

Input

First line contains one integer ​T, representing the number of testcases (or the parties Pinkie will throw, who doesn't like parties?).

The next T lines contains four integers n, x₁, x₂, x₃, representing the number of ponies who are invited to the party, and the three random number Pinkie chooses in the party.

• ​1 ≤ T ≤ 10

• Testcase #1 ~ #4 : 1 ≤ x₁, x₂, x₃ ≤ n ≤ 10⁵

• Testcase #5 : 1 ≤ x₁, x₂, x₃ ≤ n ≤ 10¹⁸

Output

For each testcase (party), please output a line contains one integer representing the number of ponies who get three balloons.

(i.e. Please print '\n' after each answer.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given sets of N points in two-dimensional space. It is guaranteed that no two points coincide in each set.

For each set, please calculate the number of lines which pass through at least three points in the set.

Input

The first line contains an integer T, representing the number of testcases (sets).

For each testcase (set) :

The first line contains an integer N, representing the number of points in this set.

The next N line contain two integer xi, yi, representing the coordinates of the i-th point. All points in the set are distinct.

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 100
• -200000 ≤ x_i, y_i ≤ 200000

Output

For each testcase (set), please output a line contains an integer representing your answer.

(i.e. Please print '\n' after each answer.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

First 5 lines describe the card. Each line contains 5 integers between 1 and 25.

( We guarantee that all 25 numbers are distinct. )

Next line contains an integer T ( 1 <= T <= 100 ), number of testcases.

Following are T testcases, and each of them contains 2 lines.

The first line of each testcase contains an integer N ( 1 <= N <= 25 ), number of selected numbers.

The second line contains N distinct selected numbers, from 1-st to N-th.

Output

For each testcase, print out an integer x, telling eccioa he can get the reward at x-th number, with x as small as possible. If he couldn't, tell him that he did not get the reward yet.

See Sample Output for more information about output format.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

HT Chen is an aspiring (also a little bit naughty) professor in NTHU. One day he felt extremely bored in his laboratory, so he decided to write down some strings on a paper. After writing down some strings, HT discovered that for some special string s, he could find two distinct indices l and r such that if he reverses the substring s[l, r], the whole string would still remain unchanged. HT found this property very exquisite, so he decided to name this kind of substring after "exquisite substring".

HT is wondering how many "exquisite substrings" are there in each string he wrote on the paper. Counting them by hand will be a dreadful work, so he decides to give extra homework so you guys can help him solve this problem.

If you can't solve this problem, HT maybe be disappointed and the upcoming midterm will become harder than usual.

** For someone who doesn't know the definition of substring : https://en.wikipedia.org/wiki/Substring 

Input

There are multiple lines in each testcase. Each line contains a string s_i that HT wrote on the paper.

The input file is ended by 'EOF'.

It is guaranteed that :

• At most 10 lines in each testcase.
• testcase #1 ~ #4 : 1 ≤ | s | ≤ 200
• testcase #5 Bonus: 1 ≤ | s | ≤ 2000

Output

For each string s_i, please output a line contains one integer representing the number of "exquisite substrings" in s_i.

(i.e. Please print '\n' after each answer.)

Sample Input  Download

Sample Output  Download

Tags

Discuss