Description

The Internet is the most important communication media nowadays. There are many powerful search engines, such as Google, Bing, and Baidu.

Dragon Tom is the king of an unknown country, whose countrymen use Google heavily to search for beautiful pictures. However, the engine is not enough for their needs. So Dragon Tom would like to create a brand new search engine, which can search for 99.99% of the beautiful pictures that his people need, and he names the engine Gogomei.

To design Gogomei, the two most significant parts are to create the keywords in the database, and to design an efficient algorithm for searching the query words among the keywords in the database. Dragon Tom has already defined the keywords based on the many beautiful pictures he has collected for about twenty years. To be a coworker of this engine, your task is to write a program for checking whether the query words are in the database or not.

Input

        First line contains a integer t which is the number of test cases.

        For each case, the first line contains a positive integer n (n <= 50,000) indicating the number of keywords in the database of Gogomei. In the next n lines, each line contains one keyword which is composed only by English letters (upper case and lower case are different) and the length of each keyword is less or equal to 30.

        After the keywords, the next line will give you a positive integer m (m <= 50,000) which is the number of queries. In the next m line, each line contains a query word and the format is the same as the keywords in the database.

Output

        For each case, output the line with the text “Case i:” without the quotes, where i is the case number starting from 1. For each query word, if the keyword is in the database, output a line with message “Yes”. Otherwise, output a line with message “No”.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

        Linear algebra is widely used in scientific computation. Dr. Lee wants to design a system for scientific computation research, and he needs your help. In particular, your task is to write a program to compute the determinant of a square matrix A (n-by-n matrix), which will be one of most frequently used operations in this system.

        However, the closed form of the determinant is too complex when n is greater than three. Dr. Lee suggests you to use the Laplace formula to calculate the determinant recursively. Laplace formula expresses the determinant of a matrix A in terms of its minors. The minor M_ij is defined to be the determinant of the (n−1)-by-(n−1) matrix that results from A by removing the i^th row and the j^th column. The expression (-1)^i+jM_ij is known as cofactor. The determinant of A, denoted by det(A), can be computed by …

        Please write a program to achieve this task.

Input

        The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases in the input.

        Following that, each case starts with an integer n (2 <= n <= 8), which indicates the size of the square matrix A. Then in the next n lines, each line contains n integers, showing the entries of each row of the matrix A. The range of values in the entries is from -5 to 5.

Output

        For each case, output one line with the determinant of matrix A.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

        Element TD is a hot game in the world of otaku, and all otakus are crazy about it. According to a CNN report, some friends even quarrel and fight because of the game. It is so terrible! To understand why this game drives people crazy, you decide to play the game now!

        Firstly, there are several maps in the game. Each map has a hole that monsters will come out from it unlimitedly. Monsters will only walk along the roads. Each road may contain up to a certain number of monsters. When a monster reaches a road junction, it will choose the next road to walk randomly.

        You have a castle to defend from monsters’ attack. To do so, you can build some towers at the road junctions to monitor the road and kill the intruding monsters. Different types of towers have different powers of killing (number of monsters that can be killed in a unit of time) and different building costs. The attack ranges of all the towers are unlimited. For example, for a tower with (power, cost) = (5, 10), then we need to pay 10 dollars to build the tower and this tower can kill 5 monsters in a unit of time.

        To be a perfect gamer, you must find the smallest cost for creating enough towers in a given map, such that you can block attacks from the monsters at any time.

Input

        The first line contains an integer t (t <= 20) that indicates the number of test cases.

        For each test case, the first line contains two integers n (2 <= n <= 70) and m (1 <= m <= n*(n-1)/2), denoting the number of intersections and the number of roads in this map, respectively. The intersections will be labeled by {1, 2, 3, …, n}.

        The next m lines are the information of the roads. Each line consists of three integers e_i, e_j, and cp(i, j). The integers ei and ej indicates that the road is from intersection i to intersection j, and the value cp(i, j) indicates that the road can contain at most cp(i, j) monsters. Each road is directed so that monsters can walk in one direction.

        The hole where monsters come out is located at intersection 1, and your castle is located at intersection n. The total number of monsters, which you will kill in a unit of time, will be less than 30,000.

        After the road information, the next line will be an integer Q (1 <= Q <= 100), indicating how many types of towers you can choose. And the following Q lines describe the information of each tower. Each line contains two integers p_i and g_i (1 <= p_i, g_i <= 1,000), which are the power and the cost of tower i, respectively. 

Output

        For each case, output a line with the minimum cost for creating enough towers.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Monkey D. Luffy is a young man who wants to become the King of the Pirates! Now he and his crew are deciding which sailing route they want to go, among the many islands in the Grand Line.

Luffy’s good friend, Nami, is the navigator of Luffy’s pirate boat Thousand Sunny. Nami wants to know all the possible sailing routes to traverse all the islands in the Grand Line. As an assistant, you need to help Nami to do this work.

Input

The first line contains a positive integer t (t <= 20), which indicates how many cases in the input. Each case starts with a positive integer n (n <= 10), which denotes the number of the islands in the Grand Line. In the next n lines, each line contains the name of an island. The length of name is at most 20, and the name is composed only by English letters.

Output

For each case, first line output the case number (See the Sample Output). Next, output all possible sailing routes in the Grand Line, and for each route, use “-” to separate two consecutive islands. Each line contains one route and the ordering of the routes can be arbitrary (See the Sample Output).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

             The Great East Japan Earthquake was a magnitude 9.0 undersea megathrust earthquake that occurred off the coast of Japan on Friday, March 11th 2011. Actually, earthquakes are frequently occurring in the world. To understand the distribution of earthquakes, the researchers in Big Research Universal Central of Earthquake (BRUCE) plan to analyze the frequency of the earthquakes in each region in the world.

            Data of the earthquakes are collected from different locations. For ease of understanding, each earthquake is represented by a blue rectangle, whose area indicates the affected range. See Figure 1 for an example.

            Each blue rectangle is represented by the coordinates in its lower-left and upper-right corners. The coordinate values are all integers. In the figure, there are three earthquakes, A, B, and C.  Earthquake A affects the region (0,1) to (4,5), earthquake B affects the region (1,2) to (6,8), and earthquake C affects the region (3,0) to (7,6). Note that the region (3, 3) to (4, 5) was affected by all the three earthquakes.

Given the data, people would like to consider different regions to live. To find the safest place, one idea is to get the maximum earthquake frequency in each of the considered region.  For instance, suppose that the considered region is (2,4) to (8,7), which is represented by the red rectangle in Figure 1. Then the sub-region (3,4) to (4,5) is affected by all three earthquakes, and achieved the maximum frequency of 3. 

Your task is to calculate the maximum frequency for any considered region R.

Input

            The input begins with t (1 <= t <= 10), the number of test cases. For each case, the first line contains two integers n (1 <= n <= 1,000), which is the number of earthquakes, and Q (1 <= Q <= 1,000), which is the number of considered regions. For the next n lines, each line contains four integers x₁, y₁, x₂, y₂ (x₁ < x₂, y₁ < y₂, 10^-9 <= x₁, y₁, x₂, y₂ <= 10⁹), which are the regions of the earthquakes. After that, the next Q lines denote the considered regions, whose format will be the same as the regions of the earthquakes.

Output

             For each considered regions, print a line with the maximum earthquake frequency in the region. Print a blank line after the output for each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

        Not The Huge Users Community Society (NTHUCS) is designing a new online game where people open shops to serve other people in a virtual world. In this game, each user needs to select a virtual country where he/she belongs to. Also, there is a map where each user needs to find a place to open his/her own shop (such as a restaurant, a post office, a bank, etc) to serve other people. Some parts of the map are reserved for the landscapes and the features, such as bridges, rivers, forests, remains …, etc. The remaining parts are empty spots that can be used for the shops.  There are also roads in the map, each road joining two empty spots. To increase the interaction between people from different countries, we wish to restrict that the two owners of the shops on the same road cannot be from the same country.        

        Eventually, each spot in the map will be occupied by some person. Your task is to write a program to check if there is at least a way that users can select their belonging countries so that the restriction can be followed.

Input

The first line of input contains a positive integer t (t <= 20), which indicates how many maps to check. For each map, the first line contains three positive integers n, m, k (n <= 50, m <= n*(n-1)/2, k <= n), indicating that there are n spots for opening shops (a spot is numbered from 1 to n) in the map, m roads, and people can select from one of the k countries. In next m lines, each line contains two integers u and v, which indicate the two end spots of a road.

Output

        For each map, output a line with “Yes” if this map can be used for this online game. Otherwise, output a line with “No”.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

      Tiyano Playstation Company (TPC) has released a popular game in Android-based cellphone. Each instance of the game has two inputs: (1) a sequence of color blocks and (2) a 2-dimensional table. See Figure 1 for an example.

Figure 1

      The target is to merge adjacent blocks in the sequence until it is left exactly one block, with such a block being a black block. The merging of two adjacent blocks will result in a new block in the same position, whose color is specified by the 2-dimensional table. For example, in Figure 1, there is a block sequence: {red, yellow, blue, red, red, …}, if we merge the first two blocks, by the merge rules in the table, we can get a green block, and the sequence will become {green, blue, red, red, …}. At each step, you can choose two adjacent color blocks to merge as long as there is a merge rule in the table.

      However, the game designer of TPC made a mistake that some instances that you will play in the game have no solution. Unfortunately, he does not know how to check for such instances, and your task is to write a program to determine if an instance is solvable.

Input

        The input begins with t (1 <= t <= 100), the number of test cases. Each test case contains three parts.

        For each test case, the first line contains two integers n (1 <= n <= 10), which is the number of colors, and m (1 <= m <= 100), which is the length of the color sequence. After that, it gives the description of the n x n 2-dimensional matrix, M, such that M_ij is the resulting color from merging color i and color j.  Each row of M is printed on a separate line. Here, we use {0, 1, 2, …, n-1} to represent the different colors in the matrix (assume 0 is black color) and M_ij = -1 indicates that color i and color j cannot be merged. After that, it contains a line with m integers, indicating the input sequence of colors.

        Take Figure 1 for example. We use {0, 1, 2, 3, 4} to represent the five colors {black, red, yellow, blue, green}, and the matrix will be:

 1 -1  4 -1 -1

 1 -1  4  0  2

-1  3 -1  3  4

 2  4  2 -1  0

-1  0  1  3  2

and the sequence of colors is: 1 2 3 1 1 2 3 0 3 1 2 1 4 4 4 0

Output

    For each test case, print the message of “Yes” or “No” without quotes to indicate if the instance is solvable or not.

Sample Input  Download

Sample Output  Download

Tags

Discuss