2014 KTU ACM ICPC Qualification Round
A. Crystals
time limit per test
0.75 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Magicians at our University want to be alchemists. They work with crystals - they can mix some set of crystals and get another set of crystals. Of course, it is needed that these changes comply with the rules because to change the set of crystals would be impossible otherwise even for magicians!

As in real life, a lot of work is needed to do to change sets of crystals. Therefore, each rule has a fixed amount of work it requires to apply.

Magicians buy potato chips and find some magical crystals in the packages. There can't exist more than one crystal of the same type, because the stronger crystal of the same type consumes the weaker and, finally, the one crystal is left.

There is a special set of crystals called "the dream set". When magician owns all crystals of the dream set and nothing more, he is very proud of that (equally to a kid who collects all puponauts).

You are given the set magician owns initially, the dream set and the rules. You need to answer whether it is possible to get only the dream set and to print the minimal needed amount of work to get it. They will decide themselves if it is worth doing.

Notes:

  • a magician can pick all his set or only a part of it when applying the rules, while he should get exactly the dream set in the end;
  • a magician can apply any number of rules and as many times as he likes.

For example, if he owns crystals {1, 2, 3} and the rule is that we can change {2, 3} to {3, 4}, the magician can get {1, 3, 4} if he wants. But that would not satisfy him if the dream set was {1, 4}.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 50).

In the first line of every test case there are two integers n (1 ≤ n ≤ 12) and m (1 ≤ m ≤ 1000) - the number of different types of crystals and the number of rules.

The set of crystals is described with the number of its elements size (1 ≤ size ≤ n) and then size number of distinct integers, which shows the types of crystals belonging to the set (0 ≤ type ≤ n - 1). All numbers are separated by spaces.

In the second line of every test case there is an initial set of crystals owned by a magician.

In the the third line there is the dream set.

In the following m lines the rules are described as “work S1 S2” - (1 ≤ work ≤ 109), S1 and S2 are the sets of crystals. The integer amount of work is needed to be done to change the set S1 to the set S2.

Output

For each test case output one line containing “Case #tc: YES work” or “Case #tc: NO” where tc is the number of the test case (starting from 1), “YES” or “NO” shows whether is it possible to get the dream set of crystals and work is the minimal amount of work which is needed to be done to get this set.

Examples
Input
2
1 1
1 0
1 0
1 1 0 1 0
3 1
2 0 1
1 2
1000000000 1 1 1 2
Output
Case #1: YES 0
Case #2: NO
B. Don't swear!
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Povilas is developing a social network called "Dwidder". He almost have it finished. However, there is one major problem. Povilas is very polite and he would never publish swear words. But you can't say that about other users of "Dwidder".

Povilas has almost solved this problem. He already prepared a dictionary which contains all the swear words. He will check every message word by word and see if any of the words are in the dictionary.

However, "Dwidder" users are pretty smart. They know that if you leave the first and last letter in place and shuffle the inside ones, the word will remain readable. For elamxpe, you can raed tihs snetence, dno't you? "Dwidder" users are not afraid to use this ability for the worse.

Povilas needs your help. He is giving you the dictionary and the words from the message. You must tell if there are swear words in the message, even if the inside letters are shuffled.

Input

The first line contains the number of test cases T (T ≤ 10). In the first line of every test case there are numbers n and m (1 ≤ n, m ≤ 1000) — the size of the dictionary and the count of words in the message. In the following line there are n strings — words from the dictionary — separated by a single space. In the next line there are m strings — words from the message — separated by a single space. Every word consists of lowercase English letters and none of them are longer than 10 characters.

Output

For each test case output one line containing “Case #tc: s”, where tc is the number of the test case (starting from 1) and s is a string consisting of zeroes and ones. The i-th character of the string corresponds to the i-th word from the message, '1' meaning that the word is a swear word and '0' that it's not.

Examples
Input
1
2 5
pig goat
pig gaot peg goat gota
Output
Case #1: 11010
C. I need some help!
time limit per test
5.5 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Hello, guys,

Could you help me to improve my program? I already posted this question on several online judges, but nobody answered. So I hope to receive an answer from you. Sorry for posting this directly to the problemset (not to my blog) :)

I don't remember the exact problem statement. But the input is 10 positive integers and I think that my program is correct. I get TLE (time limit exceeded). It might be ineffective but I don't know why.

Here is my program:


#include <cstdio>
using namespace std;

typedef long long ll;

const int mod = 1000000007;
const int Maxn = 10;

int a[Maxn];
int x;

int Tribonacci(int x)
{
if (x == 0) return 0;
if (x <= 2) return 1;
return Tribonacci(x - 3) + Tribonacci(x - 2) + Tribonacci(x - 1);
}

int Fibonacci(int x)
{
if (x == 0) return 0;
if (x == 1) return 1;
return Fibonacci(x - 2) + Fibonacci(x - 1);
}

int toPower(int x, int p)
{
int res = 1;
for (int i = 0; i < p; i++)
res = ll(res) * x % mod;
return res;
}

int friendlyFibonacciFunction(int x)
{
return toPower(Fibonacci(x + 25), Tribonacci(x + 20));
}

int myFunction(int x)
{
if (x < Maxn) return a[x];
int sum = 0, res = 0;
for (int i = 1; i <= Maxn; i++) {
sum = (sum + myFunction(x - i)) % mod;
res = (res + ll(friendlyFibonacciFunction(i)) * sum % mod) % mod;
}
return res;
}

int main()
{
for (int i = 0; i < Maxn; i++)
scanf("%d", &a[i]);
scanf("%d", &x);
printf("%d", myFunction(x));
return 0;
}

Could you submit your correct program which solves the problem correctly and effectively?

Input

The first line contains the number of test cases T (1 ≤ T ≤ 104).

In the first line of every test case there are 11 integers a0, a1, ..., a9 (1 ≤ ai ≤ 109) and x (0 ≤ x ≤ 2·109).

Output

For each test case output one line containing “Case #tc: answer” where tc is the number of the test case (starting from 1) and answer is the result of myFunction(x).

Examples
Input
2
1 2 3 4 5 6 7 8 9 10 10
1 2 3 4 5 6 7 8 9 9 9
Output
Case #1: 853943371
Case #2: 9
D. Modulo maths
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Birute loves modular arithmetics, but hates long problem statements.

Given n, find f(n).

Input

The first line contains the number of test cases T (T ≤ 50). In the following T lines there are integer values of number n (1 ≤ n ≤ 10007).

Output

For each test case output one line containing “Case #tc: num”, where tc is the number of the test case (starting from 1) and num is the value of f(n).

Examples
Input
2
1
2
Output
Case #1: 1
Case #2: 0
Note

Fun fact: 1 is neither prime nor composite number.

E. Simple sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an array (s) of positive integers having the length n.

Let's define the subarray as the array between some indexes l and r (l ≤ r and elements are sl, sl + 1, ..., sr). We call the subarray "simple" if mn is the minimal element in this subarray, mx is the maximal element in this subarray, a is a given parameter and inequality is satisfied.

You need to find the size of the biggest possible simple subarray.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 50).

In the first line of every test case there are two integers n (1 ≤ n ≤ 105) and a (1 ≤ a ≤ 109) - the size of the array and the described parameter.

In the second line of every test case there are n integers si (1 ≤ si ≤ 109) - the elements of the array.

Output

For each test case output one line containing “Case #tc: size” where tc is the number of the test case (starting from 1) and size is the size of the biggest possible simple subarray.

Examples
Input
2
2 1
1 2
2 1
1 3
Output
Case #1: 2
Case #2: 1
F. Snake++
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Everybody knows video game called "Snake". Martynas is developing an upgraded version of the original – "Snake++".

This is the game mechanics:

  • The field is rectangle, consisting of n × m squares.
  • Snake is made of head and remaining body parts. Head is steering and body parts follow the head. The length of a snake is the number of its segments (body parts plus head).
  • There is a single square, called pit, which is the starting position of the snake. At the beginning snakes head is above the ground and her body parts are in the pit below the ground. Step by step snake moves out of the pit (see the picture below). Snake is considered to leave the pit when every snake's segment occupies different square on the grid.
  • Snake moves exactly the same as in the original game: from one square to adjacent one. Snake cannot occupy a square which is already occupied by other body part of itself.
  • There are obstacles in some squares of the field. Snake cannot occupy these squares.
  • All the pieces of food are placed in the field at the start of the game. After occupying a square with food snake's length increases (see the picture below).
  • Snake can cross the boundaries of the field. That means going through the top of the field and appearing at the bottom (same for left and right boundaries).
  • There can be no more than 5 pieces of food on the field.

An example of snake's, whose starting length is 4, movement is showed in the following image (black squares are obstacles, gray squares are snake, black dot is food). In the fourth step snake have came out of the pit (you can see 4 segments of snake).

Martynas has generated some fields. The problem is that some fields are too small — snake cannot leave the pit without hitting the wall or itself. Your job is to find if the field is too small or not.

Input

The first line contains the number of test cases T (T ≤ 50). In the first line of every test case there are integers n, m and k (3 ≤ n, m ≤ 10, 2 ≤ k ≤ 5) – the height of the field, the width of the field and the starting length of the snake. In every following n lines there are m symbols: 'x' for starting pit, '#' for obstacle, little letter 'o' for food and dot '.' for unoccupied square.

Output

For each test case output one line containing “Case #tc: fit”, where tc is the number of the test case (starting from 1) and fit is text "Fits perfectly!" (without quotes) if snake can leave the pit and "Oh no, snake's too fat!" otherwise.

Examples
Input
2
3 5 5
#####
.x#..
###.#
3 5 5
#####
.x#o.
###.#
Output
Case #1: Fits perfectly!
Case #2: Oh no, snake's too fat!
G. Spells once again!
time limit per test
1.25 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Magicians can be really annoying at University. I am not sure if you have seen those types of people, but if you saw them, you would know that their favourite hobby is to throw their cast magic balls to the wall. The balls even gain some power from other magic balls!

If you asked why it is a problem, the answer is that it bothers both students (because their can't sleep during lectures as the balls have a lot of power) and a lady who needs to clear the wall every time.

Some non-magicians who are tired just because of the balls of power want to take some revenge. Of course, it is dangerous to approach all magicians, who throw balls, at once, so they want to sort things out with the magician who owns the widest range of power.

Let's call the power of the ball P.

As all magicians are unique, they can throw balls of different power (Pinitial). The number of previously thrown balls which are simultaneously located to the right and above the thrown ball is added to its power. So it can become quite powerful after that!

More formally, the final power of the ball Pfinal = Pinitial + |{i|X < xi and Y < yi}|, where (X;Y) describes the current ball coordinates, (xi;yi) describes the i-th (previously thrown) ball coordinates, for each possible i, and |S| shows the size of the set S.

It is said that the magician currently owns the range of power between 1 and Pfinal. All magicians who threw balls before can't own any power in this range (they lose some part of their range if this is the case).

For example, if the first magician owns a range (5; 7) and the second magician throws a ball of power P = 6, the first magician owns a range (6; 7) (the width is equal to 1), while the second one (1; 6) (the width is equal to 5).

You are given a list (which has size n) with the following information

  • the id of the magician;
  • the place where he casts and throws his ball of power.

You are supposed to answer which magician (to print its id) owns the widest range of power and to print the width of this range after each such throw. If there are several possibilities, choose the magician with the smallest id.

Note: it is guaranteed that each magician throws at most one ball.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 5).

In the first line of every test case there is an integer n (1 ≤ n ≤ 105) - the number of list entries.

In every following n lines there are four integer numbers id (0 ≤ id ≤ 109), Pinitial (1 ≤ Pinitial ≤ 109), x (0 ≤ x ≤ 109), y (0 ≤ y ≤ 109) - the id of the magician, the initial power of the thrown ball and the coordinates of his ball in the wall.

Note: It is guaranteed that it will be at most 1000 distinct values of x and at most 1000 distinct values of y.

Output

For each test case output one line containing “Case #tc:”, where tc is the number of the test case (starting from 1).

Then output lines “id width” - id of the magician owning the widest range and width - the maximum width of any owned range after each given throw.

Examples
Input
2
2
1 1 1 1
0 1 0 1
2
1 2 1 1
0 1 0 1
Output
Case #1:
1 0
0 0
Case #2:
1 1
1 1
H. Sugar and Salt
time limit per test
1.75 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Tomas never buys neither sugar nor salt (these are the only seasonings he use) from a shop — he makes his own. For that purpose he has Sugar-n-Salt-O-Matic. It's a special machine which produces sugar and salt, and does that simultaneously.

The Sugar-n-Salt-O-Matic is a pretty simple machine. There are some holes distributed on a plane, which are used to drop grains of seasoning. Below is a single cup which can move in any of the four directions (north, south, east or west) and be placed under any of the holes with coordinates (x, y) (0 ≤ x, y ≤ 100). At a specific time t from the hole a single grain of sugar or salt is dropped. If at that moment the cup is below the hole, the grain will fall into the cup.

There are some issues regarding this machine. At the beginning (at the time t = 0) the cup can be placed under any of the holes, but per single unit of time it can only move from current hole to the adjacent one (respecting the 4 directions movement), or stay in the same place. Also at the same time there might be multiple holes dropping grains of seasoning. This makes some of the sugar and/or salt fall onto the ground.

Obviously, the sugar is ruined even if a single grain of salt falls into the cup, and vice versa. Tomas wants only pure sugar and pure salt. Luckily, he can take the cup away at any moment of time.

Tomas must decide if he should collect sugar or salt. Given the number of holes and the timings of seasoning production find the maximum number of grains of sugar ant the maximum number of grains of salt Tomas can collect.

Input

The first line contains the number of test cases T (T ≤ 20).

In the first line of every test case there is an integer m (1 ≤ m ≤ 103) – the number of grains of seasoning dropped.

In the following m lines there are integer values of t, x, y and q (1 ≤ t ≤ 100, 0 ≤ x, y ≤ 100) – the time of the dropping, the coordinates of the hole and the type of the seasoning dropped (single lowercase character, "u" (without quotation mark) for sUgar and "a" for sAlt) — sorted in increasing order.

Note: it is guaranteed that all triples of t, x and y are pairwise distinct.

Output

For each test case output one line containing “Case #tc: sugar salt”, where tc is the number of the test case (starting from 1), sugar is the maximum number of sugar grains collected and salt is the maximum number of salt grains collected.

Examples
Input
2
5
1 1 1 a
2 1 2 u
3 1 2 u
3 1 3 a
4 2 2 u
5
1 0 0 a
1 0 1 a
1 1 0 a
1 1 1 a
2 0 0 u
Output
Case #1: 3 1
Case #2: 0 1
I. Two friends
time limit per test
1.75 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

It is not so easy to meet with your friend in the forest when you are both lost. You might ask how that would happen? Well, imagine, you are going with your friend, you are quite fast and your friend is slow. As there is a big fog, you turn around and you can't find your friend.

There is quite a shock, of course. But it is interesting to know what the expected time to meet with your friend would be, if you just waited in your place or went to any neighbouring place completely at random (with the same probability). We assume that your friend would do the same.

For example, if you are at place which has 3 neighbouring places, you would wait with the probability equal to 0.25 and you go to any of the 3 places with probability equal to 0.25. Assume, that you are doing the same operation each moment of time (as well as your friend).

You meet with your friend at the i-th place, if you and your friend happen to be at the same i-th place for the first time after some number of described steps.

The place is neighbouring to the given place if they are connected by a path.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 50).

In the first line of every test case there are two integers n (1 ≤ n ≤ 15) and m (0 ≤ m ≤ n·(n - 1) / 2) - the number of places in the forest and the number of paths. Two places have at most one path between them.

In the following m lines of every test case there two numbers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - the places connected by an undirected i-th path.

In the last line of every test case there are two integers a and b (1 ≤ a, b ≤ n) - the first friend's initial place and the second friend's initial place.

Note: the forest is not necessarily connected.

Output

For each test case output one line containing “Case #tc: exp1 exp2 ... expn” where tc is the number of the test case (starting from 1) and expi shows the expected numbers of steps to meet at the i-th place.

The answer will be considered correct if the absolute or relative error does not exceed 10 - 7 compared with the judge's answer.

If it is not possible to meet at the i-th place, print "N/A" as its expectation.

Examples
Input
2
2 0
1 2
3 2
1 2
2 3
1 3
Output
Case #1: N/A N/A
Case #2: 17.589743589744 4.800000000000 17.589743589744
J. Unnamed numbers
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Vilmantas is a real numberphile. He is fascinated by numbers, but most of all he likes numbers, which are named after famous scientist and mathematicians. For example, there are Mersenne primes (MP = 2p - 1, where p is prime), Graham's number (extremely large number, no way to define it here in commonly known notation).

Vilmantas would love to have numbers named after him. This is what he came up with. He takes some positive number and extracts every 2-digit number in the given order. For example, if we extract number 10324, we get a sequence of S = {10, 03, 32, 24}. Then he checks for three conditions:

  1. S is not empty;
  2. Every number Si must be not prime;
  3. Every neighboring numbers in S must be coprime (in other words, for every 1 ≤ i ≤ |S| - 1 greatest common divisor GCD(Si, Si + 1) must be equal to 1);

The previous number 10324 breaks two of the conditions: 3 is prime and while GCD(10, 3) = GCD(3, 32) = 1, 32 and 24 are not coprime (GCD(32, 24) = 8).

If some number satisfies all three of the conditions, then it is called Vilmantas' number.

Given numbers a and b, count the Vilmantas' numbers in range [a;b].

Input

The first line contains the number of test cases T (T ≤ 10). In the following T lines there are integers a and b (1 ≤ a ≤ b ≤ 1011).

Output

For each test case output one line containing “Case #tc: num”, where tc is the number of the test case (starting from 1) and num is the count of Vilmantas' numbers from a to b inclusive.

Examples
Input
4
1 9
23 23
25 25
100 200
Output
Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 11
Note

Only integers coprime to zero are 1 and  - 1.

K. Wolf and sheep
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

A sheep lives on an infinite field. The sheep wants to eat some grass. Grass only exists in one place. That place is a circle defined by a center point (Gx, Gy) and a radius Gr.

The sheep would gladly eat all the grass. But if you read the title of this task you noticed that there is also a wolf on that field. The wolf wants to eat the sheep, but we don't want that to happen.

The wolf is tied to a pole at position (Wx, Wy) with a rope of length Wr.

Find the area of grass that the sheep can eat without being eaten by the wolf. We can assume that the sheep starts in a safe location.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 10000).

Each test case consists of 2 lines. The first line contains integers Gx, Gy and Gr. The second line contains integers Wx, Wy and Wr. ( - 105 ≤ Gx, Gy, Wx, Wy ≤ 105, 1 ≤ Gr, Wr ≤ 105)

Output

For each test case output one line containing “Case #tc: A”, where tc is the number of the test case (starting from 1) and A is the area of grass that the sheep can eat safely with a maximum absolute or relative error of 10 - 6.

Examples
Input
2
0 0 5
0 10 5
0 0 5
5 0 5
Output
Case #1: 78.53981634
Case #2: 47.83057387