Description

Leafa drew a convex polygon. She thought the polygon is so cute so that she wanted to give it to her brother, Kirito, as a gift. But before she ever had the chance to do so Kirito spotted the cute polygon in the Leafa's computer. Kirito thought one is not enough because he loves to use dual blades in many online games he plays. So he used a simple polyline to split the convex poly-
gon into two non-empty simple polygons and saved them into two different files.
    When Leafa realized her convex polygon has been splitted she is so sad because those two simple ploygons are not as cute as the original one. So she asks you to put them back into one convex polygon. Can you help her?
    A polygon is a plane gure bounded by a nite chain of line segments closing in a loop. A convex polygon is a polygon that any line drawn through the polygon which are not tangent to a point or an edge of the polygon intersects with the boundary of the polygon exactly twice. A simple polygon is a polygon whose bondaries do not cross itself. A polyline, or a polygonal chain is a connected series of line segments. A simple polyline is a polyline that only consecutive line segments intercest and only intersecting on their ends.

Input

The first line of the input data contains an integer T (1 ≤ T ≤101) specifying the number of test cases.
    The first line of each test case contains an integers N (3 ≤ N ≤ 100,000) indicating the number of points of the first simple polygon. The N lines following contains two integers x, y each line (0 ≤ x, y ≤ 10⁹) indicating the coordinates of the points.
    The (N + 2)th line of each test case contains an integers M (3 ≤ M ≤ 100,000) indicating the number of points of the second simple polygon. The M lines following contains two integers x, y each line (0 ≤ x, y ≤ 10⁹) indicating the coordinates of the points.
    The points in a polygon are given in counterclockwise order. No two points in a polygon are at the same spot and no three consecutive points in a polygon are co-line. Note that two polygons in a test case may overlap since the coordinates may be shifted while saving the le. For at least 95 test cases, N, M ≤ 1000.

Output

For each test case, if two simple polygons cannot put back to a convex polygon due to le corruption, please output "No" on a single line. Otherwise first output "Yes" and two integers dx dy in a single line where the vector (dx, dy) indicating the movement of the second polygon so that it can join the first. If there is multiple possible solutions output the one with least dx, if still more than one possible solutions then output the least dy among the ones with the least dx. Note " " is only for clarity.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One day, Kirito found a electronic lock. He believed that there were something hidden behind that lock, so he thought he must break that lock to gain some information. After doing some research, he found that there was a secret string written on the lock { a sequence of digits like this:
1314151621391217481156718192010
Soon Kirito realized that it can be broke into pieces of distinct consecutive integers starting from one:
13, 14, 15, 16, 2, 1, 3, 9, 12, 17, 4, 8, 11, 5, 6, 7, 18, 19, 20, 10
"Maybe that is a hint to open the lock!" said Kirito. Now it's your duty to help Kirito, calculating in how many ways you can break the sequence into this format of integers?

Input

The first line of the input data contains an integer T (1 ≤ T ≤ 100) specifying
the number of test cases.
    For each test case there is a string of length at most 192, consisting of digits 0 to 9.

Output

For each test case, output a single line containing the number of possible sequences mod by 1,000,000,007.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Kirito: "Can you tell me whether string s is a palindrome or not?"
You: "Sure, it is too easy."
Kirito: "Can you tell me how many substrings of s are palindromes?"
You: "Sure, it is easy."
Kirito: "Can you tell me how many substrings of s can be arranged as a palindrome?"
You: "Sure, it is not hard."
Kirito: "Can you tell me how many substrings of a substring of s can be arranged as a palindrome?"

Input

The first line of the input data contains an integer T (1 ≤ T ≤ 250) specifying
the number of test cases.
Each test case starts with a line contains two integers n;m (1 ≤ n,m ≤ 50000), denoting the length of s and the number of queries. Then one line contains a string s which consists of only lowercase letters. Each of the following m lines contains two integers li, ri (1 ≤ li ≤ ri ≤ n), denoting a query substring s[li,...,ri] of s. No more than 5 test cases have max(n;m) > 1000.

Output

For each query, please output the number of substrings of s[li,...,ri] that can be arranged as a palindrome.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Alice plays web browser games a lot. She turns her focus on a new two player PVP game recently. The game consists of N rounds and N + 2 cards. Each card has an non-negative integer on its face while all of them having the same picture on their back sides. After two players connect to the battle field, the cards will be shued and put face down as the card pool. Then the top two cards from the pool will be placed on two initially empty card stacks face up one on each stack. Then two positive numbers w1, w2 will be randomly decided and maintain xed during the game as the weights of the stacks to nish the initial setting. Note that two players are not sharing the battle
eld but play on the identical mirror version of their own. For the rest of the game two player will play N rounds independently. In each round two players will draw the top card from the pool(two players will get the same card for the same round), look at its number and make a choice to place the card face up on top of one of the two stacks. The score gained by placing a card with number x on a stack with a top card numbered y is ws  jx - yj where ws is the stack's weight.
    Alice thought the game was purely based on luck at rst. But she soon nds out that she can never get a better score than Kirito in the game no
matter how hard she tried. Alice is sad and keep asking Kirito what's the trick behind. At last Kirito told her the secret to win. Kirito said that he
hacked into the system and he can get the following parameters before the game start: w₁, w₂, c₁, c₂, d₁, d₂, a, b, c, m. The c1 and c2 indicating the
number of initial cards on the stacks. The card drawn in the ith round would be d_i and d_i = (d_i-1 × a + d_i-2 × b + c) mod m for i > 2.
    While Kirito can determine the best strategy with there parameters, Alice decided to learn the hacking technique from Kirito and leave the strategy part to you. So your job is to write a program to tell the highest score possible given the parameters.

Input

The first line of the input data contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.
The first and only line of each test case contains eleven integers N, w1, w2, c1, c2, d1, d2, a, b, c, m (1 ≤ N ≤ 10⁷, 0 ≤ w₁,w₂ ≤ 1000, 0 ≤ a, b, c, c1, c2, d1, d2 < m ≤ 10⁸) indicating the number of rounds and the parameters of card generation(see the problem description part). Note that for at least 95% of the test cases N ≤ 10⁴.
    Please consider the card generation formula as a random number generator and has absolutely no relation to the intended solution. The intended solution works for any valid card number sequences without the mathematical restriction due to the formation of the generation formula stated.

Output

For each test case, output a single line containing the number of possible highest score.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Connect kingdom has N cities numbered 1 through N. Each city has a train station. Of course every train station is connected to all the other train stations. People in the connect kingdom build a unique, bi-directional rail route for each of these connections. One of the good sides of this system is that if some connections are out of order, they seldom becomes an issue because you can always nd a substitute route easily. Also the people are actively keeping those connections working. Based on a technical report, it's guaranteed that there is at most one broken connection connected to any single train station!
    The rail network is famous because there are many different routes to take and many di erent sceneries to see. Kirito is planning a train tour in the connect kingdom. Kirito will arrive at an arbitrarily city c0 on the first day by air. Then for each day of the following K days, he will take a train to a new city c that c > c0 and he has not visited c in this tour yet. On the last ((K +2)th) day he'll take a train from where he is to city c0 to catch the returning plane.
    Kirito wants to visit at least 3 di erent cities, i.e. K ≥ 2, and he also wants to make sure every rail connection in the planned tour is not broken. Kirito knows the list of broken rail connections and he would like to know the number of di erent possible tours under these constraints.
    He takes this question to his friend, Shinon, and ask if she can compute the number for him since Shinon is good at math (she's good at paintball too, btw). Shinon is so good at math so she proved that no matter which set of connections are broken, the number will be the same as long as the amount of broken connections is the same. Shinon's discovery simplified the problem a lot but the proof took Shinon so long that she doesn't have time to compute the number because she has to attend the International Contest of Paintball Championship. So once again it's your task to nd the number given the amount of broken rail connections. The number might be large, please mod it by 1,000,000,007.
    Two tours are different if and only if K is di erent among the two tours or there is at least one day that Kirito visits di erent cities in two tours.

Input

The first line of the input data contains an integer T (1 ≤ T ≤ 10200) specifying the number of test cases.
    The first and single line of each test case contains two integers N and M (3 ≤ N ≤ 200, 0 ≤ M ≤ N/2) indicating the number of cities and the amount of broken connections.

Output

For each test case, output a single line containing the number of possible highest score.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Destructor is a popular video game for a player can launch laser ray attack from a military satellite and destroy everything on a chosen point. Asuna is studying the strategy of the game. She managed to get some players' playing record but unfortunately she only has the inputs of the players and the scores are all lost. While Asuna's best friend, Kirito, is on a vacation in connect kingdom, she can only ask your help to simulate the game and recovery the players' scores. The game is round based and is played on a X  Y grid. Only integer lattice points (x, y) where 0 ≤ x ≤ X, 0 ≤ y ≤ Y are used. The game starts at round 1 and following phases will occur in a round while one
phase is totally executed before the next one starts:
1. Every enemy existing on the board moves to its next position specified by its moving pattern. After the movement if one enemy is out of the allowed coordinate range, it is removed from the grid and player gained no points in this case. Note that multiple enemies could be at the same coordinate at the same time.
2. If there is an enemy planned to join the grid in this round according to the script, put it on its initial position on the grid unless the hard limit of 100 enemies on the whole grid has already been reached. In the case of hard limit exceeded this new enemy will be discarded and ignored in this game play while no points awarded to the player. There will be at most one enemy in the script trying to join the grid per round.
3. Player choose a coordinate to attack, remove every enemy on that coordinate. The summation of the scores of the removed enemies are added to the player's total score.

Enemy consists of an integer score, a moving pattern and its parameters, and a time denoting which round should this enemy join the grid. The initial position of an enemy is the rst position in its moving pattern. Each possible moving pattern is detailed explained in the following section:

guard Guard has only two parameters x, y (0 ≤ x ≤ X, 0 ≤ y ≤ Y ). It will be at (x; y) all the time.

jumper Jumper has four parameters x, y, dx, dy (0 ≤ x ≤ X, 0 ≤ y ≤ Y,  -100 ≤ dx, dy ≤ 100). It will be at (x, y) initially and move the amount of vector (dx; dy) as delta each round after that. For example a jumper with parameters 1, 2, 3, -2 and join the grid at 3rd round
will be at (7, -2) at round 5.

bouncer Bouncer has four parameters x₁, y₁, x₂, y₂ (0 ≤ x₁, x₂ ≤ X; 0 ≤ y₁, y₂ ≤ Y ). Note that exactly one of x1 = x2 and y1 = y2 holds. Bouncer's initial position is (x1; y1) and will bounce between (x1; y1) and (x2; y2) at a speed of 1 grid unit per round. Note that turning is considered immediate so that bouncer will not stay at the end point for more than one round. For example a bouncer with parameters 1, 2, 1, 4 and join the grid at 3rd round will be back at its initial position at round 7, round 11 ... and so on.

teleporter Teleporter has two parameters x, y (0 ≤ x ≤ X, 0 ≤ y ≤ Y ). It's initial position is (x, y). In each round it will teleport to the position being attacked last round starting from the next round joined the grid.

avoider Avoider has two parameters x, y (0 ≤ x ≤ X, 0 ≤ y ≤ Y ). It will avoid the position being attacked last round. Assume the coordinate of the last attack is (x_atk; y_atk) and current position of avoider is (xa; ya).
The avoider will move 1 unit along +x axis if xa > xatk, 1 unit along -x if xa < xatk and no movement along x axis if xa = xatk. Same applies to y axis. So if an avoider is at (2, 4) at the end of last round and player choose to attack (3, 4) last round, avoider will move to (1, 4) this round.

Note jumper and avoider have the chance to go out of grid when moving and being eliminated. Asuna will give you the script along with the coordinates chosen by the player every round. Please report the total score to Asuna.

Input

The first line of the input data contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.
    The first line of each test case contains two integers X and Y (0 ≤ X, Y ≤ 10⁷) indicating the grid size.
    The second line contains a single integer EN (0 ≤ EN ≤ 1000) indicating the number of enemies. The following EN lines each describes an enemy, an integer time (1 ≤ time ≤ 1000) indicating the joining round, an integer score (1 ≤ score ≤ 10⁷) indicating the score and a string pattern (one of "guard", "jumper", "bouncer", "teleporter", "avoider") for the pattern type followed by the parameters of that type. These lines are sorted increasingly by time.
The following line of each test case contains an integer playtime (1  playtime  1000) indicating the number of the rounds fully played.
The next playtime lines each contains two integers x and y (1 ≤ x ≤ X; 1 ≤ y ≤ Y ). The ith line of them indicating the player's choice for
destruction coordinate at round i.
    Please note some constraints are stated in the problem description part.

Output

For each test case, output a line starts with "Total Score: " and the final total score. Note " " is for clarity.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Today, your best friends give you a graph G as a birthday present though today is not your birthday. They ask you to nd the minimum spanning tree of G in 3 seconds otherwise they will "pie" your face. You answer that question in just 0.3 seconds since it is too easy for a smart programmer like you.
    To hit back, you ask them to nd the maximum spanning tree of G in 3 seconds. But they are almost as smart as you, and answer this question in 0.31 seconds.
    One of your best friends, Kirito, is a big fan of bitwise operation. He can solve 14 queens problem in 3 seconds using bitwise operations. Now he is holding a big pie, and asking you to nd the maximum AND spanning tree of G in 3 seconds. That is, you should nd a spanning tree T such that the AND(T) is maximized, where T is the bitwise AND sum of weights of edges in T.
    For example, if there are three edges with weights 5, 6, 7 in T, we have AND(T) = 5&6&7 = 1012 &1102 &1112 = 1002 = 4.

Input

The first line of the input data contains an integer T (1 ≤ T ≤ 50) specifying the number of test cases.
Each test case starts with a line contains two integers n;m (2 ≤ n ≤ 50000; n-1 ≤ m ≤ 100000), denoting the number of nodes and edges in the undirected graph G. Each of the following m lines contains three integers ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 10⁹), which means there is an edge (ai, bi) with weight ci in G. We guarantee that G is connected, but there maybe some self-loops and/or multi-edges in G. No more than 5 test cases have max(n,m) > 1000.

Output

For each test case, please output AND(T) of the maximum AND spanning tree T of G.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Captcha authentication methods play an important role these days. It usually require users to recognize the alphabets and the number digits. But sometimes, it require users to solve an integral problem and some word riddles! One day, Kirito noticed there is a new type of Captcha challenge! It shows a strange math equation like this:
(1/n)sin x =?
    After ten minutes work, Kirito realized that the answer was 6, because the value n cancelled out!
    In order to solve these type of equation quickly, you are going to help Kirito to write a program. Kirito knows that the answer is guaranteed to be an integer in the range [0, 9], and he had already parsed the strings for you in the certain format. (Please refer to the input format.)

Input

The first line of the input data contains an integer T (1 ≤ T ≤ 100) specifying
the number of test cases.
    For each test case, there are two strings representing the numerator and
the denominator in the formula separated by a whitespace, a slash then
another whitespace. There will be only one possible unique answer, and all
strings are composed of lower case letters only. The length of each string will
be at most 100 and at least 1.

Output

For each test case, please output the answer. You may treat each letter a variable, so they can be swapped properly. For example, we know that ab = ba.

Sample Input  Download

Sample Output  Download

Tags

Discuss