Multiplication operation is not always easy! For example, it is hard to calculate 27 × 20 using your mind, but it is easier to find the answer using the following methods: 30 × 20 - 3 × 20. It turns out that people can calculate the multiplication of two special numbers very easily.
A number is called special if it contains exactly one non-zero digit at the beginning (i.e. the most significant digit), followed by a non-negative number of zeros. For example, 30, 7, 5000 are special numbers, while 0, 11, 8070 are not.
In this problem, you are given two numbers a and b. Your task is to calculate the multiplication of a and b (a × b), by writing the multiplication expression as a summation or subtraction of multiplication of special numbers. Can you?
The first line contains an integer T (1 ≤ T ≤ 104) specifying the number of test cases.
Each test case consists of a single line containing two integers a and b ( - 109 ≤ a, b ≤ 109, a ≠ 0, b ≠ 0), as described in the problem statement above.
For each test case, print a single line containing the multiplication expression of a and b as a summation or subtraction of multiplication of special numbers. All special numbers must be between - 109 and 109 (inclusive). If there are multiple solutions, print any of them. It is guaranteed that an answer always exists for the given input.
The multiplication expression must be printed in exactly one line. A single term must be printed as 
in which z and w are both special numbers, # represents a single space, and x represents the multiplication operation. Two consecutive terms must be printed as 
in which z and w are both special numbers, # represents a single space, 
represents the multiplication operation, and 
represents either the addition operation + or the subtraction operation - . (Check the sample output for more clarification).
2
55 20
70 17
60 x 20 - 5 x 20
-3 x 70 + 70 x 20
A rooted tree is a tree with a countable number of nodes, in which a particular node is distinguished from the others by being the ancestor node of every node of the tree. This node is called the root node.
You are given a rooted tree consisting of n nodes numbered from 1 to n. The root of the tree is node number 1. Each node i has a value vi assigned to it.
For each subtree, you must find the minimum number of nodes you must change the value on them to any other value so that the distance between every pair of nodes in that subtree is equal to the absolute difference between the values on them, or say that it is impossible. Can you?
The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the number of nodes in the tree. Then a line follow containing n integers v1, ..., vn (1 ≤ vi ≤ 105), in which vi is the value of the ith node.
Then n - 1 lines follow, each line contains two integers ai and bi (1 ≤ ai, bi ≤ n), giving an edge between nodes ai and bi.
For each test case, print a single line containing n space-separated integers x1, ..., xn, in which xi is the answer of the subtree of node i. If an answer does not exist for a subtree, print - 1.
1
2
1 3
1 2
1 0
Today, Husam was visiting his grandmother. Husam always takes a path such that the total distance he will walk is as minimum as possible. Husam decided to give you all information about his journey so that you can find the total distance he walked.
Husam grandmother's home is a kilometers away from Husam's home to the south, and b kilometers away to the west. Also, there is a river located c kilometers away from Husam's home to the east.
Before Husam visiting his grandmother, he went to the river to fill his bottle with water. After this, he then went directly to his grandmother's home. After Husam finished his visit, he followed the direct straight path between his grandmother's home and his home. When Husam walked x% of that path, he remembered that his bottle is empty, so, he went to the river to fill it, then he went to his home.
Husam needs your help to calculate the distance he walked today. Can you?
The first line contains an integer T (1 ≤ T ≤ 105) specifying the number of test cases.
Each test case consists of a single line containing four integers a, b, c and x (1 ≤ a, b, c ≤ 109, 0 ≤ x ≤ 100).
Consider the ground and the river as a flat land, and the length of the river is limitless. Also, you can consider Husam and his grandmother homes as small points.
For each test case, print a single line containing the total distance Husam walked during his journey.
Your answer will be considered correct if its relative or absolute error does not exceed 10 - 9.
1
6 2 3 18
20.225553719
Asem has a wooden fence consisting of n boards, in which n is an odd number. Asem wants to paint this fence using two colors; black and white, such that the first board will be painted black, the second board will be painted white, the third board will be painted black, and so on.
Asem has black paint that can paint at most x boards and white paint that can paint at most y boards. Your task is to determine if you can paint the whole fence or not. Can you?
The first line contains an integer T (1 ≤ T ≤ 104) specifying the number of test cases.
Each test case consists of a line containing three integers n, x, y (1 ≤ n, x, y < 109), in which n is an odd number specifying the number of boards in the fence, x is the maximum number of boards that can be painted in black, and y is the maximum number of boards that can be painted in white.
For each test case, print a single line containing "YES" (without quotes) if you can paint the whole fence. Otherwise, print "NO" (without quotes).
3
5 3 3
7 2 3
9 6 2
YES
NO
NO
Abed is so motivated this year, his goal is qualifying for the ACM International Collegiate Programming Contest (ACM ICPC). Therefore, he always trains using Codeforces online judge. If you do not know Codeforces, the following rules can help you to understand how it works:
- Each problem has a set of n tests numbered from 1 to n. The first k tests are called sample tests. These tests are visible in the problem statement and a user can see them all.
- When Abed gets a wrong answer on test x (x ≤ n), he can see all the tests up to test number x. If Abed gets accepted, he can see all the tests.
- Each test can be either small or big. Abed can see the entire test only if it is small. If the test is big, Abed can see it partially. All the sample tests are small.
For example, let us consider a problem contains 6 tests, in which the first two tests are the sample tests. If Abed got a wrong answer on test 4, a wrong answer on test 3, and a wrong answer on test 5, he can see all tests from 1 to 5. If test 3 is small and the tests from 4 to 6 are big, Abed can see the first three tests fully, but he cannot fully see the remaining tests.
Unfortunately, Abed usually gets a lot of wrong answers. A submission made by Abed is called stupid if he got a wrong answer on a small test that he can see it fully. You are given a list of submissions made be Abed, your task is to count how many stupid submission Abed has made. Can you?
The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.
The first line of each test case contains three integers n, m, and k (1 ≤ k ≤ n ≤ 104, 1 ≤ m ≤ 104), in which n is the number of tests in the problem, m is the number of submissions Abed has made, and k is the number of sample tests. Then a line follow contains n characters t1, ..., tn, in which ti is 'S' if the ith test is small, and 'B' if it is big.
Then m lines follow, giving the list of submissions Abed has made, such that the ith line will either contain a single character 'A' if Abed got accepted on the ith submission, or contain a character 'W' and an integer x (1 ≤ x ≤ n) giving that Abed got a wrong answer on test case x.
For each test case, print a single line containing the number of stupid submissions Abed has made.
2
5 4 2
S S B S B
W 3
W 4
W 4
A
4 3 2
S S B B
W 1
W 2
W 3
1
2
Being a judge is not always an interesting job! For example, it is very boring to wait for the first submission in the contest. So, judges used to entertain themselves using the "I'm Bored" tab in the PC2 software. In this tab, a button is shown and you need to click it (if you can!).
Since Alaa has been a judge in many contests, the "I'm Bored" tab is also boring to her, so, she decided to play a new game in today's contest. Alaa brings with her a huge bag full of lowercase English letters, and she starts playing with them. Alaa goal is to build a list of palindrome strings of the same length such that each string does not contain the same character more than two times.
After 3 minutes of playing, Alaa wondered what is the longest string's length that she can build? And what is the maximum number of strings the list can contain? When Alaa brings her notebook to calculate the answers, she starts receiving dozens of submissions. So, she gives you her bag and asks you to find the answers for her. Can you?
The first line contains an integer T (1 ≤ T ≤ 104) specifying the number of test cases.
Each test cases consists of a line containing 26 integers f1, ..., f26 (0 ≤ fi ≤ 109), in which fi is how many letters i Alaa has. The letters are numbered from 1 to 26 starting from 'a'.
For each test case, print a single line containing two integers x and y, in which x is the length of the strings in the group and y is the size of the group.
2
2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 1
4 2
A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "madam" or "racecar".
You are given a grid consisting of n rows each of which is dived into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each cell is identified by a pair (x, y), which means that the cell is located in the row x and column y.
Your goal is to delete a row x (1 < x < n) and a column y (1 < y < m), after this the matrix will be divided into 4 parts. Let us define the beauty of each part as the maximum value inside it. Your task is to choose x and y such that the difference between the largest and smallest beauties is as minimal as possible. Can you?
The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.
The first line of each test case contains two integers n and m (3 ≤ n, m ≤ 500), specifying the grid size, in which n is the number of rows and m is the number of columns.
Then n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 109 (inclusive).
For each test case, print a single line containing the minimum difference between the largest and smallest beauties after dividing the matrix into 4 parts.
2
3 3
9 5 8
3 4 1
6 2 7
4 4
22 7 3 11
3 1 8 9
5 2 4 3
13 5 6 9
3
13
You are given two strings a and b consisting of lowercase English letters. A beautiful substring is defined as a substring of any length of string b such that the first and last letters of it are the same as the first and last letters of any substring of length k of string a.
Your task is to count the number of beautiful substrings. Can you?
The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.
The first line of each test case contains three integers n, m, and k (1 ≤ n, m ≤ 105, 1 ≤ k ≤ n), in which n is the length of string a, m is the length of string b, and k is the described variable in the statement.
Then two lines follow, the first line contains a string a of length n and the second line contains a string b of length m. Both strings consist only of lowercase English letters.
For each test case, print a single line containing the number of beautiful substrings
2
4 5 3
acbd
abcbd
3 3 1
kkd
dkd
3
4
A substring of a string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), in which n is the length of the string s.
There are n students working on a secret project, this project is very important and unique, so they decided to keep it safe, and protect it from leakage.
The students will put all the project's documents in a cabinet that has x locks, and each student will take a set of y unique keys, such that each key can open only one lock. The cabinet can be opened if and only if m or more of the students are present.
Each of the cabinet's lock has an infinite number of keys that can open it, and students may have different or similar sets of keys. In order to open the cabinet, z students must be presented (m ≤ z), such that these students have at least one key for each cabinet's lock.
Your task is to find minimum values of x and y. More formally, your task is to find what is the minimum number of locks needed and what is the minimum number of keys to the locks each student must carry such that the cabinet can be opened if and only if m or more of the students are present. Since these numbers are large, you need to print them modulo 109 + 7.
The first line contains an integer T (1 ≤ T ≤ 105) specifying the number of test cases.
Each test case consists of a single line containing two integers n and m (1 ≤ m ≤ n ≤ 105), in which n is the number of students, and m is the minimum number of students that must be present to open the cabinet.
For each test case, print a single line containing two integers x and y, in which x is the smallest number of locks needed, and y is the smallest number of keys to the locks each student must carry. Both numbers must be printed modulo 109 + 7.
4
3 2
2 2
5 4
5 3
3 2
2 1
10 4
10 6
In the first test case, there are 3 students, and at least 2 of them must present to open the cabinet. The optimal answer is to use 3 locks for the cabinet, such that each student will take 2 keys as follow: the 1st student takes keys of the 1st and 2nd locks, the 2nd student takes keys of the 1st and 3rd locks, and the 3rd student takes keys of the 2nd and 3rd locks. This distribution will ensure that at least two students must present in order to unlock all locks and open the cabinet.
Yousef loves playing with functions in his free time. Today, he invents the following function:
Yousef will give you a list of queries, and you need to find the answers for them. For each query, you are given an integer n, and your task is to count the number of integers m in which (0 ≤ m ≤ n) and calc(n, m) is an even number. Can you?
The first line contains an integer T (1 ≤ T ≤ 105) specifying the number of test cases.
Each test case consists of a single line containing an integer n (0 ≤ n ≤ 1018), as described in the problem statement above.
For each test case, print a single line containing the number of integers m in which (0 ≤ m ≤ n) and calc(n, m) is an even number.
2
1
2
0
1
You are given two strings a and b of the same length and consisting of lowercase English letters. You can pick at most one subsequence of string b and do a cyclic shift on that subsequence exactly once.
For example, if you have a string "abcdefg" and you picked the letters at indices 2, 5, and 6 as a subsequence to do a cyclic shift on them, the letter at index 2 will go to index 5, the letter at index 5 will go to index 6, the letter at index 6 will go to index 2, and the string will become "afcdbeg".
Your task is to check if it is possible to make string b equivalent to string a using at most one cyclic shift. Can you?
The first line contains an integer T (1 ≤ T ≤ 200) specifying the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 105) specifying the length of strings a and b. Then two lines follow, giving strings a and b, respectively. Both strings consist only of lowercase English letters.
For each test case, print a single line containing "YES" (without quotes) if it is possible to make string b equivalent to string a using at most one cyclic shift. Otherwise, print "NO" (without quotes).
2
6
abcdef
adcebf
4
abcd
dabd
YES
NO
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence 
is a subsequence of 
obtained after removal of elements 
, 
, and 
.