ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)
A. Zero Array
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a consisting of n elements, and q queries. There are two types of queries, as follow:

  • "1 p v" – An update query asks to change the value at position p in array a to v.
  • "2" – A query asks to print the minimum number of required operations to convert array a to a zero array.

A zero array is defined as an array which all its elements are zeros. There is only one allowed operation to convert an array to a zero array. At each operation, you can choose a value x and subtract it from all non-zero elements in the array, such that no element will be negative after the operation.

Input

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line of each test case consists of two integers n and q (1 ≤ n, q ≤ 105), in which n is the size of the array a, and q is the number of queries.

Then a line follows containing n elements a1, a2, ..., an (0 ≤ ai ≤ 109), giving the array a.

Then q lines follow, each line containing a query in the format described in the problem statement. It is guaranteed that the following constraints hold for the first type of queries: 1 ≤ p ≤ n, 0 ≤ v ≤ 109.

The sum of n and q overall test cases does not exceed 106 for each.

Output

For each query of the second type, print the minimum number of required operations to convert array a to a zero array. The queries must be answered in the order given in the input.

Example
Input
1
5 5
3 2 1 5 4
1 2 3
2
1 3 2
1 4 1
2
Output
4
4

B. New Assignment
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a class consisting of n students, in which each one has a number representing his/her personality. The teacher gives the students a new assignment and asks them to solve it in groups so that each group can contain two students at most.

Students cannot create groups as they please because the teacher gives the following rules that must be met in order for a group to be valid:

  • The group can be composed of one male student, one female student, or male and female students.
  • If the number of students in the group is two, these students must share common interests. Two students i and j share interests if and only if their numbers ai and aj share common divisor d > 1.

Since this is a really diverse class, no triple of students share a common interest, therefore all triples ai, aj, ak are co-primes (i.e. gcd(ai, aj, ak) ≡ 1).

Your task is to distribute the students into groups such that each student must join exactly one group, and the number of groups is as minimal as possible. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 104), in which n is the number of students in the class.

Then a line follows containing n integers a1, a2, ..., an (1 ≤ ai ≤ 106), in which ai if the personality of the ith student. Then a line follows containing n space-separated characters p1, p2, ..., pn (), in which pi is "M" if the ith student is male, and "F" if she is female.

The sum of n overall test cases does not exceed 3 × 105.

Output

For each test case, print a single line containing the minimum number of groups that can be formed in the class.

Example
Input
2
2
3 6
M F
5
5 6 7 10 21
F F F M M
Output
1
3
Note

In the second test case, the minimum number of groups is 3, in which the first group consists of the 1st and 4th students, the second group consists of the 2nd student, and the third group consists of the 3rd and 5th students.

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

In this problem, you are given two permutations a and b of n numbers, and you need to play a game with them! In this game, you are required to perform the following steps:

  1. For each number x, draw a line segment connecting between its positions in the given permutations.
  2. Count the number of intersections between the line segments.

For example, let us consider two permutations (5, 4, 2, 1, 3) and (2, 5, 4, 1, 3). The following picture shows the permutations after drawing all line segments. In the picture, the number of intersections between the line segments is 2.

Given the permutations a and b, your task is to play the game and to count number of intersections between the line segments. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the size of permutations.

Then a line follow containing n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n), giving the first permutation a.

Then a line follow containing n distinct integers b1, b2, ..., bn (1 ≤ bi ≤ n), giving the second permutation b.

The sum of n overall test cases does not exceed 7 × 105.

Output

For each test case, print a single line containing the number of intersections between the line segments.

Example
Input
2
5
5 4 2 1 3
2 5 4 1 3
4
1 2 3 4
1 2 4 3
Output
2
1

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

In many contests, balloons are used to indicate to contestants the general state of the contest. Each time a team solves a problem, a balloon of a specific color is sent to the team and attached on or near their machine. As the contest progresses, the contest floor gradually fills up with a multi-colored display showing how various teams are doing in the contest.

Consider a contest of n problems in which each problem is attached to a specific balloon color. You will be able to see the balloon color of a problem in the contest floor if at least one team solved it during the contest.

You are given the number of accepted solutions on each problem. Your task is to count how many different colors you will be able to see. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 1000), in which T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 20), in which n is the number of problems in the contest.

Then a line follows containing n integers p1, p2, ..., pk (0 ≤ pi ≤ 100), in which pi is the number of accepted solutions on the ith problem.

Output

For each test case, print a single line containing the number different colors will you be able to see in the contest's floor.

Example
Input
3
4
5 7 2 1
3
1 0 1
5
4 0 1 0 3
Output
4
2
3

E. Maximum Sum
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a grid consisting of n rows each of which is dived into n columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to n 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. All cells in the grid contain positive integers.

Your task is to choose a subset of the grid's cells, such that their summation is as maximal as possible, and there are no two adjacent cells in that subset. Two cells are considered adjacent if they are horizontal, vertical, or diagonal neighbors.

Input

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line contains an integer n (1 ≤ n ≤ 16), in which n is the number of rows and columns in the grid.

Then n lines follow, each line contains n integers, giving the grid. All values in the grid are between 1 and 1000 (inclusive).

Output

For each test case, print a single line containing the maximum sum of a subset of the grid's cells. The chosen subset must not contain any adjacent cells.

Example
Input
2
2
4 7
2 9
3
1 2 3
4 5 6
7 8 9
Output
9
20

F. Working Time
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Working time is the period of time that a person spends at paid labor.

You are given the working record of an employee containing the starting and ending time of work in n days. Your task is to determine if that employee worked sufficiently during these n days. An employee is considered to be worked sufficiently if the total number of working hours during the n days is at least m hours.

Input

The first line contains an integer T (1 ≤ T ≤ 300), in which T is the number of test cases.

The first line of each test case contains two integers n and m (1 ≤ n ≤ 100) (0 ≤ m ≤ 2400), in which n is the number of working days, and m is the minimum number of required working hours during these n days.

Then n lines follow, each line contains two strings s and e, in which s is the starting time of work, and e is the ending time of work. Both times are given in the format hh:mm, where hh represents the hours and mm represents the minutes. It is guaranteed that the ending time is not less than the starting time, and both times will be in one day. Times are given in 24-hour time notation.

The sum of n overall test cases does not exceed 2 × 104.

Output

For each test case, print "YES" if the employee is considered to be worked sufficiently. Otherwise, print "NO".

Example
Input
3
2 15
08:00 16:00
07:55 16:12
2 20
08:00 18:30
07:30 17:00
3 35
10:00 16:00
08:05 16:37
11:07 15:30
Output
YES
YES
NO
Note

In the 24-hour time notation, the day begins at midnight, 00:00, and the last minute of the day begins at 23:59.

In this problem, the ending minute is not counted. For example, consider a person who started working at 00:00 and fished at 00:10, then the total number of working minutes is 10.

G. Hard Equation
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider the following equation

Given a, b and m, your task is to find a value x that satisfy the equation for the given values. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 500), in which T is the number of test cases.

Each test case consists of a line containing three integers a, b and m (0 ≤ a, b < m ≤ 109).

Output

For each test case, print a single line containing an integer x (0 ≤ x ≤ 1017) that satisfy the equation , for the given a, b and m.

If there are multiple solutions, print any of them. It is guaranteed that an answer always exist for the given input.

Example
Input
3
3 9 11
2 3 5
2 1 5
Output
2
3
4

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

In geometry, a cube is a three-dimensional solid object bounded by six square faces, with three meeting at each vertex. The image bellow is an example of a cube.

You are given the surface area of a cube, and your task is to find the length of that cube's edge. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 1000), in which T is the number of test cases.

Each test case consists of a line containing an integer a (1 ≤ a ≤ 6 × 106), giving the surface area of a cube.

Output

For each test case, print a single line containing the length of the given cube's edge.

It is guaranteed that all answers are integer numbers. Do not print any floating-point values.

Example
Input
2
24
6
Output
2
1

I. Circles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let d be the diameter of a circle with center c = (a, b). A square has been drawn inside that circle such that its vertices lies at the circle's circumference. Four circles have been drawn on the square's sides such that the diameter of each circle is the side of the square, as shown in the figure below.

Your task is to calculate the shaded area in the figure for a given d. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 105), in which T is the number of test cases.

Each test case consists of a line containing an three integers a, b, and d ( - 109 ≤ a, b ≤ 109) (1 ≤ d ≤ 109), giving the center and the diameter of a circle.

Output

For each test case, print a single line containing shaded area.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Example
Input
1
2 3 8
Output
32

J. Smallest Difference
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a consists of n elements, find the maximum number of elements you can select from the array such that the absolute difference between any two of the chosen elements is  ≤ 1.

Input

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line of each test case consist of an integer n (2 ≤ n ≤ 104), in which n is size of the array a

The a line follow containing n elements a1, a2, ..., an (1 ≤ ai ≤ 104), giving the array a.

Output

For each test case, print a single line containing the maximum number of elements you can select from the array such that the absolute difference between any two of the chosen elements is  ≤ 1.

Example
Input
2
3
1 2 3
5
2 2 3 4 5
Output
2
3

K. Citations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A citation is a reference to a published or unpublished source. This source can be a book or an article. For example, if you are writing a new article discusses the Advanced Encryption Standard (AES) you may add a reference to the AES Proposal: Rijndael, which contains the detailed description of the algorithm from the authors. Each article or book may contain multiple citations that are provided after the end of the content.

One of the most exhausting things is to prepare the format of the citations because each journal has different requirements for the citations section. In this problem, you will help all the researchers in the world by providing an automated method to prepare the citations for them.

Usually, the citations are placed in a file named BibTeX file. This file consists of a list of citations, such that each citation is represented as follow:

Each entry in the BibTeX file is consisting of 8 sections, which are: author, title, journal, year, volume, number, pages, and publisher.

To generate a human-readable format of the citations, the BibTeX file is compiled and the information it contains will be used to show the human-readable format of the citations in following structure:

author. title. journal. year;volume(number):pages.

Thus, the above citation will be shown as follow:

An. D, Da. F, Ne. R, Br. S, Pa. M. Evaluating the power consumption of wireless sensor network applications using models. Sensors. 2013;13(3):3473-3500.

Notice that all the information provided in the BibTeX file was used as it is given in the file except for the author section. Each author name will be converted so that the first two letters of author’s first name and the first letter of the author’s last name will be taken and concatenated with a dot and space in between (i.e. ". "), as shown in the example above.

You are given a BibTeX file contains n citations, and your task is to convert them to the human-readable format. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 1000), in which n is the number of citations in the BibTeX file. Then n citations follow, giving a BibTeX file. The format of each citation will be as the picture shown in the statement. Please check the sample input for more clarification.

It is guaranteed that no section will be empty and no white spaces will exist outside the curly braces of each section (i.e. {}), and each section will be on a separate line. Also, volume, number, and year sections will contain only integer values. Moreover, the format of the pages section is always "x-y", in which x and y are the starting and ending pages, respectively. Both x and y are integer values. Finally, each author's name consists of two space-separated names; the first and the last names. Both names are non-empty strings consisting of English letters such that the first letter of each name is uppercase and the remaining letters are lowercase. The length of author's first name is at least 2 letters. The author's section may contain multiple authors, these authors will be separated by a comma and space (i.e. ", ").

Sections inside each citation are not given in a specific order. The length of each section’s line is at most 120.

Output

For each citation, print a single line containing the human-readable format. Each citation must be printed in one line only and without any extra spaces.

Example
Input
1
2
@article{
title={Testing},
author={Ahmed Salem},
journal={Planta},
volume={10},
number={7},
pages={20-30},
year={2016},
publisher={Springer}
}
@article{
journal={Proofs from THE BOOK},
pages={55-58},
volume={9},
number={11},
author={Ahmed Salem, Ali Ramadan},
title={WSN},
year={2010},
publisher={Springer}
}
Output
Ah. S. Testing. Planta. 2016;10(7):20-30.
Ah. S, Al. R. WSN. Proofs from THE BOOK. 2010;9(11):55-58.