Description

Mr. Kim is a professional programmer. Recently he wants to design a new editor which has as many functions as possible. Most editors support a simple search function that finds one occurrence (or all occurrences successively) of a query pattern string in the text.

He observed that the search function in commercial editors does nothing if no query pattern is given. His idea of a new search function regards each substring of the given text as a query pattern string itself and his new function finds another occurrence in the text. The problem is that there can be occurrences of many substrings in the text. So, Mr. Kim decides that the new function finds only occurrences of the longest substring in the text in order to remedy the problem. A formal definition of the search function is as follows:

Given a text string S , find the longest substring in text string S such that the substring appears at least twice. The two occurrences are allowed to overlap.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. For each test case, a text string S is given in one line. For every string, the length is less than or equal to 5,000 and the alphabet Σ is the set of lowercase English characters.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print the length of the longest substring in text string S such that the substring appears at least twice.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mobile phones prevail in everyday life. Every mobile phone has a number pad for users to dial the telephone number. Figure 1 shows a typical layout of number pads, which can be represented as 4 by 3 rectangular cells. We know that some mobile phone numbers are easy to memorize, since entering in sequence of digits implies an easy-to-remember geometric figure.

For each phone number, we can make a corresponding geometric figure, Phone Plot, which is a sequence of connected line segments. Assume that a phone number with n digits is d₁ d₂ d₃...d_n-1 d_n . The first line segment of Phone Plot is a line segment connecting the center points of pad d₁ and pad d₂ . The second line segment of Phone Plot connects the center points of pad d₂ and d₃ . In a similar way the k -th line segment connects the center points of pad d_k and pad d_k+1 , and the last segment connects d_n-1 and d_n .

Let us show a few examples. The Phone Plot for the number 1023289873 is shown as the thick lines in Figure 2(a). Figure 2(b) shows that the Phone Plot for a number 1159533969.

You should note that some connecting line segments may overlap other line segment collinearly.

We characterize a Phone Plot by the Minimal Number of Decomposing Segments(MNDS). MNDS is the minimal number of line segments to reconstruct the given Phone Plot. So we easily find that the MNDS of the number 1023289873 is 5, and the MNDS of 1159533969 is 3. If the Phone Plot is reduced to a single point for a number (e.g., 0000000000), then MNDS of such a point Phone Plot is defined 0.

We want to classify the phone number into three disjoint classes; EXCELLENT, GOOD and BAD by the complexity of Phone Plot. Thus if the MNDS of Phone Plot is at most 3, then this number is classified to EXCELLENT. If MNDS is exactly 4, then this number is classified to GOOD. If the MNDS is greater than or equal to 5, that number is classified to BAD.

According to this classification, we say 1023289873 is BAD and 1159533969 is EXCELLENT. Figure 3 shows another example with 5233999008. Since the MNDS of 5233999008 is 5, so this number is BAD.

You have to decide whether the phone number given is EXCELLENT or GOOD or BAD according to the MNDS of the Phone Plot.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a string representing a phone number. The length of a phone number string is greater than 5 and less than 20.

Output

Your program is to write to standard output. For each test case, print EXCELLENT or GOOD or BAD in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The famous Korean internet company nhn has provided an internet-based photo service which allows The famous Korean internet company users to directly take a photo of an astronomical phenomenon in space by controlling a high-performance telescope owned by nhn. A few days later, a meteoric shower, known as the biggest one in this century, is expected. nhn has announced a photo competition which awards the user who takes a photo containing as many meteors as possible by using the photo service. For this competition, nhn provides the information on the trajectories of the meteors at their web page in advance. The best way to win is to compute the moment (the time) at which the telescope can catch the maximum number of meteors.

You have n meteors, each moving in uniform linear motion; the meteor m_i moves along the trajectory p_i + t×v_i over time t , where t is a non-negative real value, p_i is the starting point of m_i and v_i is the velocity of m_i . The point p_i = (x_i, y_i) is represented by X -coordinate x_i and Y -coordinate y_i in the (X, Y) -plane, and the velocity v_i = (a_i, b_i) is a non-zero vector with two components a_i and b_i in the (X, Y) -plane. For example, if p_i = (1, 3) and v_i = (-2, 5) , then the meteor m_i will be at the position (0, 5.5) at time t = 0.5 because p_i + t×v_i = (1, 3) + 0.5×(-2, 5) = (0, 5.5) . The telescope has a rectangular frame with the lower-left corner (0, 0) and the upper-right corner (w, h) . Refer to Figure 1. A meteor is said to be in the telescope frame if the meteor is in the interior of the frame (not on the boundary of the frame). For example, in Figure 1, p₂, p₃, p₄ , and p₅ cannot be taken by the telescope at any time because they do not pass the interior of the frame at all. You need to compute a time at which the number of meteors in the frame of the telescope is maximized, and then output the maximum number of meteors.

Input

Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers w and h (1 ≤ w, h ≤ 100, 000) , the width and height of the telescope frame, which are separated by single space. The second line contains an integer n , the number of input points (meteors), 1 ≤ n ≤ 100, 000 . Each of the next n lines contain four integers x_i, y_i, a_i , and bi ; (x_i, y_i) is the starting point p_i and (a_i, b_i) is the nonzero velocity vector v_i of the i -th meteor; x_i and y_i are integer values between -200,000 and 200,000, and a_i and b_i are integer values between -10 and 10. Note that at least one of a_i and b_i is not zero. These four values are separated by single spaces. We assume that all starting points p_i are distinct.

Output

Your program is to write to standard output. Print the maximum number of meteors which can be in the telescope frame at some moment.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Jisung is the student representative of the Department of Computer Engineering in ACM University. A few days later, the annual festival will be held for the students in the department. He is preparing some events for the festival. Since Jisung likes to make and solve puzzles, he decides to devise some interesting puzzle for the festival.

The followings are the rules for the puzzle made by Jisung:

(1) The players will be given an integer n . Then they should use the first n capital letters from the Roman alphabet. For example, if n = 4, the four characters A, B, C, and D will be used to solve this puzzle.

(2) The players will be given s forbidden strings. No forbidden string contains another forbidden string as a substring. The winner is the student who makes the longest string that does not include a forbidden string as a substring.

(3) If such a longest string does not exist, i.e., if we can make arbitrarily long strings that satisfy the above condition, or if we cannot make any string that satisfies the above condition, “No” should be answered.

For example, suppose the given number n = 2 , i.e., the players can use the two characters A and B. Assume that the forbidden strings are {AAA, AB, BA, BB}. In this case, the longest string that does not include any of the four forbidden strings as substrings is AA. But if the given forbidden strings are {AAA, BBB, ABAB, BBAA}, we cannot make such a longest string since arbitrarily long concatenations of ABA, i.e., ABAABAABA ... do not include any forbidden string.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers n (1 ≤ n ≤ 26) and s (1 ≤ s ≤ 1, 000) which represent the number of characters and the number of forbidden strings, respectively. From the second line to (s + 1) -st line of the test case, the forbidden strings are given one by one. The length of a forbidden string does not exceed 50.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print the longest string that does not include any forbidden string as a substring if it exists, otherwise, just print “No” as output. When there exists more than one such longest string with the same length, print the lexicographically largest string among them.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Joe works in a maze. Unfortunately, portions of the maze have caught on fire, and the owner of the maze neglected to create a fire escape plan. Help Joe escape the maze.

Given Joe's location in the maze and which squares of the maze are on fire, you must determine whether Joe can exit the maze before the fire reaches him, and how fast he can do it.

Joe and the fire each move one square per minute, vertically or horizontally (not diagonally). The fire spreads all four directions from each square that is on fire. Joe may exit the maze from any square that borders the edge of the maze. Neither Joe nor the fire may enter a square that is occupied by a wall.

Input

The first line of input contains a single integer, the number of test cases to follow. The first line of each test case contains the two integers R and C, separated by spaces, with 1 <= R,C <= 1000. The following R lines of the test case each contain one row of the maze. Each of these lines contains exactly C characters, and each of these characters is one of:

• #, a wall
• ., a passable square
• J, Joe's initial position in the maze, which is a passable square
• F, a square that is on fire

There will be exactly one J in each test case.

Output

For each test case, output a single line containing IMPOSSIBLE if Joe cannot exit the maze before the fire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are competing in a ski slalom, and you need to select the best skis for the race. The format of the race is that there are N pairs of left and right gates, where each right gate is W metres to the right of its corresponding left gate, and you may neither pass to the left of the left gate nor to the right of the right gate. The i^th pair of gates occurs at distance y_i down the hill, with the horizontal position of the i^th left gate given by x_i. Each gate is further down the hill than the previous gate (i.e. y_i < y_i+1 for all i).

You may select from S pairs of skis, where the jth pair has speed s_j. Your movement is governed by the following rule: if you select a pair of skis with speed s_j, you move with a constant downward velocity of s_j metres per second. Additionally, at any time you may move at a horizontal speed of at most v_h metres per second.

You may start and finish at any two horizontal positions. Determine which pair of skis will allow you to get through the race course, passing through all the gates, in the shortest amount of time.

Input

The first line of input contains a single integer, the number of test cases to follow.

The first line of each test case contains the three integers W, v_h, and N, separated by spaces, with 1 <= W <= 10⁸, 1 <= v_h <= 10⁶, and 1 <= N <= 10⁵.

The following N lines of the test case each contain two integers x_i and y_i, the horizontal and vertical positions respectively of the ith left gate, with 1 <= x_i, y_i <= 10⁸.

The next line of the test case contains an integer S, the number of skis, with 1 <= S <= 10⁶.

The following S lines of the test case each contain one integer s_j, the speed of the j^th pair of skis, with 1 <= s_j <= 10⁶.

Output

Output one line for each test case. If it is impossible to complete the race with any pair of skis, print the line IMPOSSIBLE. Otherwise, print the vertical speed s_j of the pair of skis that allows you to get through the race course in the shortest time.

Sample Input  Download

Sample Output  Download

Tags

Discuss