Practice Contest #1
A. Two Palindromes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A string is a palindrome if it can be read the same in both directions. For example, "madam" is a palindrome while "sir" is not.

Given two strings, each of which is a palindrome. Find if it is possible to merge all the letters of the two string in one palindrome string. That is, you need to find if it is possible to put all letters of the two strings together in one string and order them in some way to get a palindrome.

For example, if we have the two strings "abba" and "qq", we can merge them to "aqbbqa", which is a palindrome. Note that you can merge the two strings in any way, but you are not allowed to remove any of the characters.

Input

The input consists of two lines, each contains a non-empty string of no more than 100 lowercase English letters.

It is guaranteed that each of the given strings is a palindrome.

Output

Print a single line with YES if it is possible to merge the two strings into a palindrome. Otherwise, print NO.

You can print each letter in any case (upper or lower).

Examples
Input
abba
qq
Output
YES
Input
a
c
Output
NO
Input
bab
weew
Output
YES

B. Is It Easy ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

ArabellaCPC's Judges decided to print the problem statements.

Each one of the $$$n$$$ participated teams will get exactly one copy of the problem-statements, and each copy costs $$$k$$$ coins.

How many coins it will cost judges to print exactly one problem-statements for each team.

Input

The input consists of two integers $$$n$$$ and $$$k$$$, $$$(1 \leq n,k \leq 1000)$$$

Output

print the total cost of all problem statements.

Examples
Input
5 3
Output
15
Input
4 1
Output
4

C. Cinema
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Rami and K of his friends are going to watch a movie tonight. There are only one row that contains some available seats, all other rows are taken. Given the description of this row, Rami wants to know if he can find consecutive seats available to sit with his friends.

Input

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

The first line of each test case consists of two-separated integers C, K (1 ≤ C, K ≤ 105), the number of seats in the row and the number of friends going with Rami, respectively.

The second line contains a string of C digits, where 0 represents an empty seat, and 1 represents taken one.

Output

For each test case, print a single line with yes if Rami can find a place for him and his friends, otherwise print no.

Example
Input
2
5 2
10101
6 3
000011
Output
no
yes

D. Primes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A prime number is a natural number greater than 1 and has exactly 2 divisors which are 1 and the number itself.

You are given a prime number $$$n$$$, find any 2 prime numbers $$$a$$$ and $$$b$$$ such that $$$a+b=n$$$ or state that no such pair of primes exists.

Input

The input contains a single prime number $$$n$$$($$$2 \le n \le 10^7$$$).

Output

If there doesn't exist any 2 primes such that their summation is equal to $$$n$$$ then print -1, otherwise print the 2 primes on a single line separated by a space.

Examples
Input
5
Output
2 3
Input
11
Output
-1

E. ACM Student Chapter (A)
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

The ACM Student Chapter created a new Facebook group to answer the questions of the students currently taking the Structured Programming course.

Dr. Ibrahim asked the group administrators to answer any question within at most 3 hours. So, if a question is posted at time 08:04:02, one of the admins must post a reply strictly before 11:04:02.

Although Dr. Ibrahim is not a member in the group, he has a spy that sends him everyday a summary of when the questions were asked and when they were answered.

Write a program that allows Dr. Ibrahim to know automatically if all questions were answered within 3 hours or not.

Input

The first line of input contains an integer N (1 ≤ N ≤ 50) representing the number of questions.

Each of the following N lines contains the time at which one of the questions was posted, followed by a space, then the time at which the reply was posted.

The format of the time is: HH:MM:SS (00 ≤ HH ≤ 23), (00 ≤ MM, SS ≤ 59).

It’s guaranteed that the given data is valid (no reply precedes its post) and within one day.

Output

Print “Yes” if all the questions were answered within 3 hours, otherwise print “No”.

Examples
Input
3
00:00:00 01:30:25
00:58:33 02:24:45
18:16:42 21:16:41
Output
Yes
Input
3
00:00:00 01:30:25
00:58:33 02:24:45
18:16:42 21:16:42
Output
No
F. ACM Student Chapter (B)
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

One day, Dr. Ibrahim noticed that some questions were answered after 3 hours and decided to increase the number ACM admins that answer questions on the group.

ACM admins are really good at Structured Programming. It takes any admin exactly 15 minutes to answer any question, but they can’t answer more than one question at the same time. For example, if an admin starts working on a question at time 03:00:00, he will answer at time 03:14:59 and will be free to start working on another question at 03:15:00 or later.

Given the summary of the posts of one day, find the minimum number of admins required to answer all the questions, such that each question is answered within 3 hours.

Input

The first line of input contains an integer N (1 ≤ N ≤ 100,000) representing the number of questions.

Each of the following N lines contains the time at which one of the questions was posted.

The format of the time is: HH:MM:SS (00 ≤ HH ≤ 23), (00 ≤ MM, SS ≤ 59). Note that all of the given data is within one day, but not necessarily sorted. All questions must be answered within 3 hours even if it was posted at 23:59:59 (in this case, the answer will be in the next day).

Output

Print the minimum number of admins Dr. Ibrahim has to assign so that all the questions are answered within 3 hours.

Examples
Input
3
03:22:15
00:42:08
18:49:22
Output
1
G. Matryoshka Dolls
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Matryoshka Dolls are Russia's most popular souvenirs. They are sets of wooden figurines of decreasing size placed one inside another, though they have the same exact shape.

Our Matryoshka Doll is known to have an integer size $$$S$$$ which is the largest doll size in the collection, and each doll should have size $$$X$$$ times less than the doll that holds it($$$\textrm{size of the doll} \le \frac{\textrm{size of the doll that holds it}}{X}$$$).

Given $$$S$$$ and $$$X$$$, What is the maximum number of dolls that can be nested inside each other.

Input

The first and only line contains $$$2$$$ integers $$$S,X$$$($$$1 \le S \le 10^9$$$ , $$$2 \le X \le 10^9$$$).

Output

Output one integer, the maximum number of dolls.

Example
Input
10 2
Output
4

H. Birthday Puzzle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Today is the Birthday of a beautiful girl, she's happy and she's telling her friends loudly to bring her birthday gifts. One of her best friends who is fond of puzzles decided to bring her a very special gift, a magic box, this box cannot be opened unless the beautiful girl solves the mysterious puzzle written on the box and writes the answer on a small piece of paper under where the puzzle is written.

"You are given an array $$$a$$$, the answer is obtained by doing OR operation to the numbers in each subset of array $$$a$$$, then by summing all the subset ORing results". Help the beautiful girl to find the answer so she can open the magic box and continue celebrating her blessed birthday.

Input

The first line contains integer $$$n(1\le n \le 20),$$$ the size for array $$$a$$$ The second line contains $$$n$$$ integers, $$$a_{i}(1 \le a_{i} \le 10^5)$$$ the array $$$a$$$ elements

Output

Help the beautiful girl to find the answer for the puzzle.

Example
Input
3
1 2 3
Output
18
Note

Note: a subset of an array $$$a$$$ is another array that can be obtained by removing zero or more elements from $$$a$$$.

The first sample subsets:

1

2

3

1|2 = 3

1|3 = 3

2|3 = 3

1|2|3 = 3

Answer = 1+2+3+3+3+3+3 = 18

Where | is the OR operation.

For more information about the OR operation use this link: https://en.wikipedia.org/wiki/Bitwise_operation#OR

I. Winning Cells
time limit per test
1 second
memory limit per test
256 megabytes
input
chess.in
output
standard output

You and your friend decided to play a new game using a squared chessboard of size n × n and one rook. Rows are numbered from 1 to n from top to bottom, and columns are numbered from 1 to n from left to right. Each cell is identified by a pair (r, c) which means that the cell is located at row r and column c.

The rules are simple, you and your friend will take turns, and you will start first. In each turn a player can move the rook at least 1 cell, and at most k cells in only one direction, either up or left, without going outside the chessboard. The player who moves the rook to the top-left cell (1, 1) wins.

You will choose the starting position for the rook. You are not allowed to choose the top-left cell. If you both will play optimally, how many cells can you choose as a starting position to win the game.

Input

The first line of input contains an single integer T (1 ≤ T ≤ 2 × 104), the number of test cases.

Each test case consists of a single line that contains two space-separated integers n and k (1 ≤ k < n ≤ 109), where n is the size of the chessboard, and k is the maximum allowed move.

Output

For each test case, print a single line that contains the number cells you can choose as a starting position to win the game.

Example
Input
3
2 1
3 1
9 4
Output
2
4
64

J. Qwerty78 Trip
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Qwerty78 is a well known programmer (He is a member of the ICPC WF winning team in 2015, a topcoder target and one of codeforces top 10).

He wants to go to Dreamoon's house to apologize to him, after he ruined his plans in winning a Div2 contest (He participated using the handle "sorry_Dreamoon") so he came first and Dreamoon came second.

Their houses are presented on a grid of N rows and M columns. Qwerty78 house is at the cell (1, 1) and Dreamoon's house is at the cell (N, M).

If Qwerty78 is standing on a cell (r, c) he can go to the cell (r + 1, c) or to the cell (r, c + 1). Unfortunately Dreamoon expected Qwerty78 visit , so he put exactly 1 obstacle in this grid (neither in his house nor in Qwerty78's house) to challenge Qwerty78. Qwerty78 can't enter a cell which contains an obstacle.

Dreamoon sent Qwerty78 a message "In how many ways can you reach my house?". Your task is to help Qwerty78 and count the number of ways he can reach Dreamoon's house. Since the answer is too large , you are asked to calculate it modulo 109 + 7 .

Input

The first line containts a single integer T , the number of testcases.

Then T testcases are given as follows :

The first line of each testcase contains two space-separated N , M ( 2 ≤ N, M ≤ 105)

The second line of each testcase contains 2 space-separated integers OR, OC - the coordinates of the blocked cell (1 ≤ OR ≤ N) (1 ≤ OC ≤ M).

Output

Output T lines , The answer for each testcase which is the number of ways Qwerty78 can reach Dreamoon's house modulo 109 + 7.

Examples
Input
1
2 3
1 2
Output
1
Note

Sample testcase Explanation :

The grid has the following form:

Q*.

..D

Only one valid path:

(1,1) to (2,1) to (2,2) to (2,3).