2015 ACM Syrian Collegiate Programming Contest
A. My Friend of Misery
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

With the SCPC2015 getting closer, Noura Boubou, SCPC Head of Media, was very busy to the extent of not having time to recharge her phone's credit balance. However, her best friend, Nicole, was kind enough to transfer her own credit for the sake of keeping Noura online 24/7.

The phone credit transfer system in Syria works in the following way: Each successful transfer operation withdraws 25 extra credit units from the sender's balance, but it doesn't cost anything when a transfer operation is unsuccessful due to non sufficient credit balance.

Given the log of credit transfer requests and the response from the system to each request, in the form: Amount of transfer, and result of operation (either successful or unsuccessful), can you find out the number of possible initial credit balance values that Nicole could have had which satisfy the given log file?

Note that the initial credit balance is always a non negative integer.

Input

The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.

The first line of each test case contains an integer N (1 ≤ N ≤ 105), the number of operations in the log of credit transfer requests.

Each of the following N lines contains an integer mi (1 ≤ mi ≤ 106), the amount of credit to transfer, followed by .

  • { + } denotes a successful operation.
  • { - } denotes an unsuccessful operation.

Each log contains at least one unsuccessful operation.

Output

For each test case, print a single line that contains the number of possible initial credit balance values that Nicole could have had.

Examples
Input
3
3
512 -
128 +
256 +
4
80 +
70 +
200 -
150 +
3
100 -
100 -
540 -
Output
103
50
125
Note

Warning: large Input/Output data, be careful with certain languages.

B. Brother Louie
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In August 2015, coach Fegla was visiting Syria for a training camp in AAST, Lattakia Branch, as Noura and Fegla are very close friends, she asked him whether her brother Tamim can attend the camp since he has been a contestant for a year. Tamim was very interested in the coach's topics. One day, Tamim was trying to implement a binary tree drawing software, he asked the coach for some hints, and the coach suggested the following technique:

Given a rooted full binary tree (each node, except the leaves, has exactly two children nodes), the program must draw a tree where the nodes are circles with radius r, and the center of the root is located at (0, 0).

The drawn tree should satisfy the following conditions:

  • The distance between a node and its left child is equal to the distance between the node and its right child.
  • The horizontal distance between two subtrees rooted at two nodes with the same parent node must be equal to H.
  • The horizontal distance between two subtrees is the difference between the X coordinate of the rightmost point on the circumference of a node in the left subtree, and the X coordinate of the left most point on the circumference of a node in the right subtree.
  • The vertical distance between a node and its children must be equal to V, this distance is calculated between the circumferences as in the horizontal distance.
Help Tamim test his program by answering queries about the coordinates of some node U after his program has drawn the tree using the given parameters; r, V, H.
Input

The first line of input contains an integer T (1 ≤ T ≤ 64), the number of test cases.

The first line of each test case contains two integers N and q (1 ≤ N, q ≤ 105), the number of nodes and the number of queries. Each of the following N lines contains .

  • If k = 0 then the ith node is a leaf node.
  • If k = 2 then the ith node is a parent node and two integers will follow, the left child L, then the right child R (1 ≤ L, R ≤ N).
Then q lines follow, each line will represent a query. Each query will be given in the format: r V H U, (1 ≤ r, V, H ≤ 104), (1 ≤ U ≤ N)
Output

For each test case, print q lines, each line should contain the coordinates of the given node U rounded to 4 decimal places.

Examples
Input
1
9 4
2 4 5
2 6 7
2 1 2
0
0
2 9 8
0
0
0
1 2 1 2
1 2 1 9
2 2 2 5
2 2 2 7
Output
4.1250 -4.0000
0.3750 -12.0000
-5.2500 -12.0000
12.7500 -12.0000
Note

Warning: large Input/Output data, be careful with certain languages.

C. Everything
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Since Noura Boubou is one of the best photographers in the ACPC, she attends most events, and takes a lot of pictures. Her photos, therefore, are scattered in different unorganized folders in her external hard drive.

During the preparation for SCPC2015, she needed specific photos from her hard drive, so coach Fegla advised her to install a program called "Everything" that works in the following way:

The search tool takes a text as an input, and outputs  -  in lexicographical order  -  all the file names that has the entered text as a prefix. Note that the empty string is a prefix of any file name.

Given the names of the files on the hard drive. For each file, find the minimum number of moves needed to find and select the file using this search tool.

Here is the set of the allowed moves: {UP, DOWN, HOME, END, TYPE one letter}.

At the beginning, the focus is on the search box, after typing the needed prefix (zero or more characters), pressing DOWN will select the first result, after that, you can move down or up in the list, pressing END will move you to the last result, and pressing HOME will move you to the first one.

Note that you need to press DOWN at least once (before pressing HOME / END / UP) to move from the search box to the list of results.

For each file, the process starts all over again from the search box.

For example, we can find and select the file "scpc" in two moves as follows (check the pictures):
  • The first window shows that all files are displayed because the search box is empty.
  • The second window shows that after typing the letter 's', all files with prefix "s" are displayed.
  • The third window shows that after pressing DOWN the first item is selected and in this example it's the file we want.
Input

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

The first line of each test case contains an integer N (1 ≤ N ≤ 105), the number of files on the hard drive. Then N lines follow, each line contains the name of one of the files.

  • Each file name consists of lowercase English letters only (a-z).
  • No two files have the same name.
  • The length of any file name is at least 1 and at most 105.
  • Total number of characters in one test case doesn’t exceed 5 × 105.
Output

For each test case print N space - separated integers on a single line, the ith number is the minimum number of moves needed to find and select the ith file.

Examples
Input
2
5
scpc
acm
syria
acpc
accepted
5
feglathegreat
candidatesamerraed
masterhossamyousef
candidateabdullahbahosain
masterhassanalhamsh
Output
2 2 2 3 1
2 2 2 1 2
Note

Warning: large Input/Output data, be careful with certain languages.

D. Secure but True
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Since both Nicole and Noura are admins for the ACPC page, they need to agree on a secure and easy way to exchange password information whenever one of the admins changes it, therefore, Nicole suggested the following technique for doing it:

Let L be the list of all strings that contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y}, sorted by their length. If two strings have the same length, they are sorted according to the alphabetical order.

Help Nicole and Noura by writing a program that finds the new password. Given a string S that contains only mirrored letters, the new password is the string in L that is located after the string S by K.

Input

The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.

Each test case will consist of an integer K (1 ≤ K ≤ 109), followed by the string S (1 ≤ |S| ≤ 103).

|S| represents the length of the string S.

Output

For each test case, print the new password on a single line.

Examples
Input
4
2 M
4577 ATM
491 AI
132 A
Output
T
ITMO
MAX
AAA
Note

Warning: large Input/Output data, be careful with certain languages.

E. Going in Circles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

During the SCPC2015 celebration, and as Noura likes to keep everyone entertained, she wanted to play a game with the students and volunteers. She asked them to stand in a circle in order to assign them into 2 groups.

The rules for forming the two groups are:

  • Every student must be a member of exactly one of the two groups.
  • A volunteer can be a member of at most one group.
  • Students from the same university should be in the same group (even if that means the inequality in size of the two groups).
  • The members of each group should form a non-empty contiguous part of the circle.
  • Groups should be formed without changing the order of the students and volunteers in the circle.
The university of a student will be represented by uppercase English letters (A-Z), and the university of a volunteer will be represented by lowercase English letters (a-z).

Given a string that you should treat as a circle (which means that the last letter is a neighbor to the first one), calculate the number of ways to choose two ordered, non - overlapping substrings that represent the two groups and satisfy the given rules.

Input

The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.

Each test case will consist of a single line that contains a string S (2 ≤ |S| ≤ 104).

|S| represents the length of the string S.

Output

For each test case, print the number of ways on a single line.

Examples
Input
3
AbB
AcMsCpC
syria
Output
8
36
100
Note

Warning: large Input/Output data, be careful with certain languages.

F. Hey JUDgE
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Since Judge Nicole Hosh moved to Egypt for her Computer Science Masters in AASTMT, in 2014, she has been training with coach Fegla and attending his camps in Egypt. She, also, set a number of problems for TCPC and JCPC and was a judge in LCPC and SCPC. Her best friend Noura was so proud of her so she was trying to convince her to start writing Codeforces Div. 2 round. After various attempts to convince her, Nicole finally agreed, and so, she started collecting some problems with different difficulties from her ex-contestant friends.

Judge Nicole collected 7 ideas for problems of different levels, she wants to create 5 problems for the next contest, one for each difficulty level, from A to E (difficulty 1 to 5). Given the difficulty level of the problems she currently has, she can merge the ideas of two problems, one of level x, and the other of level y to get a problem of level x + y.

For example, Judge Nicole can merge two problems of difficulties A and D, to get one problem of difficulty E (1 + 4 = 5).

Merging more than two problems into one will produce a problem with a long statement which is hard to explain, so she won’t do this (i.e., each problem is merged with another at most once). Also, she can’t merge a resultant problem again, and she can't use the same problem twice.

Input

The first line of input contains an integer T (1 ≤ T ≤ 330), the number of test cases.

Each test case will contain only one string S of length 7. Each letter of the string represents the difficulty level of a problem (from A to E), 'A' is the easiest and 'E' is the hardest.

Output

For each test case print "YES" if she can prepare a contest using the current problems, otherwise print "NO".

Examples
Input
3
EBEABDA
CEDEACA
BDAAEAA
Output
YES
NO
YES
Note

Warning: large Input/Output data, be careful with certain languages.

G. Paradise City
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Noura has been looking for a restaurant to host the SCPC2015 celebration in Lattakia, she decided that the best method to pick a restaurant is according to the number of contestants that are living near it. Given a grid representing the map of Lattakia, each 3x3 cells represent a district, each district will consist of 3x3 areas. The center of each district is a restaurant (X), other cells can be: 


  ‘.’ denotes an empty block.
  ‘*’ denotes a block full of people (4 persons)
Help Noura decide which restaurant to choose by finding the maximum number of students living in a district.
Input

The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.

The first line of each test case contains an integer N (1 ≤ N ≤ 100), the number of districts. Then follows three lines, each consists of 3 × N characters, representing the map of the city of N districts.

Output

For each test case, print the maximum number of students living in a district on a single line.

Examples
Input
3
3
***...***
.X.*X*.X.
***...***
2
*.*.*.
.X..X*
*.*.*.
3
.*...****
*X**X**X*
...*..*.*
Output
24
16
28
Note

Warning: large Input/Output data, be careful with certain languages.

H. Another Square in the Floor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While planning the SCPC2015 contest floor, each team has been assigned an area of a rectangular shape. The area covers the maximum region the team is allowed to move around during the contest.

When Noura saw the contest floor, she didn't like the rectangular shapes. She asked the organizers to reassign each team for a square shaped area instead of a rectangular one.

Given the sides of a rectangle, help the organizers find the square with minimum area, that covers the rectangle. To make it easier for the organizers, each side of the square must be parallel to one of the sides of the rectangle.

Input

The first line of input contains an integer T (1 ≤ T ≤ 1024), the number of test cases.

Each test case contains two space-separated integers X, Y (1 ≤ X, Y ≤ 1000), the dimensions of the rectangular shaped area.

Output

For each test case, print on a single line, the area of the square described in the problem statement.

Examples
Input
3
3 3
5 7
12 6
Output
9
49
144
Note

Warning: large Input/Output data, be careful with certain languages.

I. Home Sweet Home
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

While Coach Fegla and Noura were flying back home from Marrakech after attending the ICPC2015 World Finals, they got really bored in their 6 - hour plane trip, so the coach decided to tell Noura some cool information about binary numbers and operators, and he gave her this challenge to pass the time.

Coach Fegla asked her if she could find the number of ways to choose two integers, A and B, such that (L ≤ A, B ≤ R) and the XOR of the binary representations of A and B (without leading zeros) is palindrome in binary.

For example, , after removing leading zeros 101 is palindrome.

Input

The first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.

Each test case will contain two space - separated integers L, R (0 ≤ L ≤ R ≤ 1012).

Output

For each test case print the number of ways on a single line.

Examples
Input
3
1 4
0 0
4 8
Output
12
1
15
Note

A string of binary digits is a palindrome if it can be read the same from either direction.

For example: 0, 11 and 10101 are palindromes, while 10 and 10011 are not.

means XOR, remember that:

Warning: large Input/Output data, be careful with certain languages.

J. Smooth Developer
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Noura has been recently working on developing Android Applications with coach Alaa Jrad. One of her tasks was to develop an application to help coach Alaa with teaching Geometry to his contestants, so she decided to use coach Fegla's geometry library, as it is one of the best in the region. But while using coach Fegla's geometry library, if you need the code of the function IsPointOnSegment, for example, you will also need to include the function collinear in the code. In a similar manner, the function collinear might yet require other functions to run.

Given the dependencies of each function, and the list of the functions Noura will use, help her find the names of all the functions she needs to include from the library to get her code to compile.

Input

The first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.

The first line of each test case contains two space - separated integers N (1 ≤ N ≤ 105), the number of functions in the library, and K (1 ≤ K ≤ N) the number of the functions Noura will use. Then N lines follow, each line will be in the following format:

Si Ci Fi, 1 Fi, 2 ... Fi, Ci

Where Si represents the name of the ith function, Ci (0 ≤ Ci ≤ i) represents the number of functions the ith function depends on, then followed by a list of Ci distinct function names, each represents the name of a function the ith function depends on. It's guaranteed that all function names in the list appeared in the input before. A function can depend on itself (recursive function).

The last line of each test case contains K distinct function names, the list of the functions that Noura is going to use.

Function name doesn't exceed 15 letters and contains only lowercase and uppercase English letters.

Output

For each test case, print the functions Noura needs to include, each on a single line, following the same order of appearing in the input file.

Examples
Input
2
2 1
cross 0
polygonArea 1 cross
polygonArea
6 2
intersect 0
circlePoint 0
intLines 1 intersect
circleThree 1 intersect
circleTwo 0
mec 3 circlePoint circleTwo mec
intersect mec
Output
cross
polygonArea
intersect
circlePoint
circleTwo
mec
Note

Warning: large Input/Output data, be careful with certain languages.

K. Betrayed
time limit per test
5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Noura and Judge Mohammad Asaad were in SCS working together when Mohammad decided to betray Noura and leave her to work alone because he couldn't resist participating in the CodeJam.

Noura was very understanding because she knows how much he loves competing. He decided to submit the solution for a problem based on DFS (Depth First Search - See notes below). The input file for this problem contains number of trees with undirected edges and his code will be tested on all of them. After downloading the input file he discovered that his program crashes because of stack overflow, since he must update his code very quickly before the timeout of submitting this problem expires, he decided that instead of starting the DFS from node 1, he will start it from a randomly chosen node (all nodes have the same probability to be chosen).

Assume that the solution takes one second to be run to compute the answer for each tree, if the program crashes it will take Mohammad 3 more seconds to re-run it and in this case the solution should be re-run starting from the first tree.

Mohammad gets stack overflow if the depth of his recursive function exceeds K.

What is the expected number of seconds to pass all trees without getting stack overflow?

Input

The first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.

Each test case will start with a line that contains two space - separated integers, C (1 ≤ C ≤ 20), the number of trees of the downloaded input file, and K (1 ≤ K ≤ 105), the maximum depth that does not cause stack overflow. Each of the following C lines represents a tree in the downloaded input file. Each tree is written in the following format:

n a2 a3 a4... an, (1 ≤ n ≤ 105), (1 ≤ ai ≤ n)

Where n is the number of nodes and ai indicates an undirected edge between ai and i.

It's guaranteed that in any given tree, at least 25% of its nodes will not cause stack overflow if Mohammad starts the DFS from them.

Output

For each test case print a single number, the expected number of seconds to pass all trees without getting stack overflow, rounded to 4 decimal places.

Examples
Input
3
2 2
2 1
3 1 1
3 5
7 3 4 7 1 5 6
6 1 4 2 1 5
5 1 1 5 1
4 3
4 4 1 1
6 1 2 1 1 5
5 4 1 3 4
1
Output
2.0000
4.6000
6.5000
Note

Below is the psuedocode for a recursive implementation of DFS: 


  procedure DFS(G,u):
      label u as discovered
      for all edges (u, v) in G do
          if vertex v is not labeled as discovered then
              recursively call DFS(G,v)

The depth of the starting node is 0.

Warning: large Input/Output data, be careful with certain languages.

L. Chance
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After Noura's brother, Tamim, finished his junior training, coach Fegla was impressed with his progress. He told Noura that if Tamim would solve the following problem in SCPC2015 and yet does not qualify to the ACPC2015, he will give him a chance to participate unofficially in it.

The problem goes as follows:

Given L and R, how many integers between them have a prime number of ones in their binary representation?

Can you help Tamim participate in the ACPC2015?

Input

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

Each test case will consist of two space - separated integers: L and R (0 ≤ L ≤ R ≤ 105).

Output

For each test case, print the number of integers between L and R that have a prime number of ones in their binary representation.

Examples
Input
3
2 10
1 19
3 101
Output
6
13
65
Note

Warning: large Input/Output data, be careful with certain languages.

M. ACPC Headquarters : AASTMT (Stairway to Heaven)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As most of you know, the Arab Academy for Science and Technology and Maritime Transport in Alexandria, Egypt, hosts the ACPC Headquarters in the Regional Informatics Center (RIC), and it has been supporting our region with all kinds of resources it can provide, whether it was hosting nationals, regionals, or providing support for national contests around the Arab Region by sending its employees and students to participate in preparing contest systems, coaching, problem setting, and whatever these nationals ask for. However, ACPC's volunteers' schedules can get very busy, therefore, some conflicts might occur between the nationals they are assigned to help with. As to resolve these conflicts, Noura suggested that the SCPC2015 students can come up with a program that detects the conflicts in the contests' schedule, and that is, detect for each volunteer whether they have been assigned to multiple contests running at the same time.

Given the requirements for each contest (contest name, start date, end date, number of required volunteers, volunteers' names), print a list of volunteers' names that have conflicts in their schedules, sorted in alphabetical order.

Input

The first line of input contains an integer T (1 ≤ T ≤ 64), the number of test cases.

The first line of each test case contains an integer N (1 ≤ N ≤ 100), the number of contests.

Each of the following N lines contains one contest's data: Contest name C, start date S, end date E, number of required volunteers V, followed by V distinct volunteers' names.

Names consist of lowercase Latin letters, and their length doesn't exceed 10 letters.

You may assume that (1 ≤ S ≤ E ≤ 365) and (1 ≤ V ≤ 100).

Output

For each test case, print the number of volunteers that have conflicts in their schedules, followed by the names of the volunteers in alphabetical order, each on a single line.

Examples
Input
2
2
lcpc 3 7 4 fegla compo fouad nicole
scpc 5 11 3 fegla fouad nicole
2
jcpc 8 10 2 fegla hossam
scpc 10 15 3 fegla fouad nicole
Output
3
fegla
fouad
nicole
1
fegla