2015 USP Try-outs
A. Bridge
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Bridge is a great card game! The 2006 World Youth Team Championship in Bridge took place in Thailand, the same country that will host the 2016 ICPC World Finals! Let's describe the rules of bridge. The game is played with a standard 52-card deck, with 13 cards from each of the four suits (hearts, spades, clubs, and diamonds). The cards are ranked as A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2, with the ace having the highest rank and 2 the lowest. There is also a predetermined trump suit (H = hearts, S = spades, C = clubs, D = diamonds, NT = no trump).

The game is played by 4 players (N, E, S, W), as shown in the figure, and it has several rounds, called tricks. A player starts a round/trick by playing a card. Afterwards, each player plays a card, following clockwise order, until everyone has played. The trick then ends. The leading player in the trick can play whichever card she or he wants; this card's suit is defined as the current trick's suit. Every player other than the leading player must play a card of the same suit as the current trick's, unless she or he has no such card. In this case, the player can play any card.

The winner of a trick is defined as follows. If a trump card (a card of the trump suit) has been played, the winner is the player who played the highest ranking trump card. Otherwise, the winner is the player who played the highest ranking card of the trick's suit. The winner of a trick starts the next trick.

Player N starts the first trick. Players N and S play as a team, as do E and W. The goal is to win the most tricks.

In this problem, each player has R cards and we would like to know how many tricks team NS can win if everyone plays optimally.

Input

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

Each test case starts with a line containing a string (one of H, S, C, D) representing the trump suit and an integer R representing the number of cards each player is dealt. The next 4 lines each contain a space-separated list of R cards. A card is represented as a string XY, where X is one of A, K, Q, J, T (representing 10), 9, 8, 7, 6, 5, 4, 3, 2, and Y is the suit (one of H, S, C, D). The 4 lines contain the hands of the players N, E, S, and W, in this order. Note that no card appears twice!

Limits

  • 1 ≤ T ≤ 100
  • 1 ≤ R ≤ 4
Output

For each test case print a single integer, the maximum number of tricks that the NS team can win.

Example
Input
2
S 1
2H
AH
2S
KH
NT 1
2H
AH
2S
KH
Output
1
0

B. Renzo and the palindromic decoration
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

At the ruins of Wat Phra Si Sanphet (วดพระศรสรรเพชญ), one can find famous inscriptions that have only recently been decoded. Several numbers written using Thai numerals decorate these ruins.

A couple of years ago, the famous Peruvian researcher Renzo "el intrépido" Morales found out that most numbers found at the ruins are palindromic, that is, they represent the same number when read backwards. For instance, 171 is palindromic, whereas 17 is not.

Intrigued by the existence of non palidromic numbers as decorations in the ruins, Renzo found out that, while these numbers are not palindromic when represented in base 10 (which is the base used in the Thai numeral system), they are palindromic when represented in another base. For b > 0, the base-b representation of a number N is the sequence amam - 1... a1a0 so that 0 ≤ ai ≤ b - 1 for each 0 ≤ i ≤ m, am ≠ 0, and

ambm + am - 1bm - 1 + ... + a1b + a0 = N.
For the previous example, the base-2 representation of 17 is 10001, which is palindromic.

To validate his discovery, Renzo wants you to write a program that takes a number represented in base 10 and checks in which bases from 2 to 16 such number has a palindromic representation.

Input

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

Each test case has a single line with an integer N written in base 10.

Output

For each test case, print in a single line a space-separated list of integers, from 2 to 16 and in increasing order, of the bases for which the representation of N is palindromic. If N does not have a palindromic representation for any of the bases from 2 to 16, print -1.

Limits

  • 0 ≤ T ≤ 103
  • 0 ≤ N < 231
Example
Input
2
17
2570
Output
2 4 16
4 16

C. Robotics Competition
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Malai advanced to the Thai national robotics contest finals, to be held next week. Each contestant specifies an instruction to her or his robot and the number of times this instruction should be executed. The robot that gets to closest to a certain target wins the contest.

Each robot is represented by a point (x, y) and it starts at the origin of the plane. Each instruction is defined as I(α, ), where α is an angle in degrees and  a distance in meters. To execute instruction I(α, ), the robot must rotate α degrees counterclockwise around the origin and then move  meters to the right from its position.

The image shows the execution of the instruction I(90, 10) three times.

Malai is a newbie at this contest and needs your help to find the robot's final position.

Input

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

Each test case contains a single line with an angle α, a distance  and an integer n, the number of times that the instruction I(α, ) must be executed. You can assume α and are rational values.

Limits

  • 1 ≤ T ≤ 500
  • 0 ≤ n ≤ 109
  • 0 ≤ α < 360
Output

For each test case, print one line with the coordinates (x, y), in meters, of the final position of the robot, after n executions of the instruction I(α, ). The error should not be greater than 10 - 4.

Example
Input
4
90 10 1
90 10 2
90 10 3
30 1.5 121
Output
10 0
10 10
0 10
1.5 0

D. Random walks in Thailand
time limit per test
10 s
memory limit per test
64 megabytes
input
standard input
output
standard output

Thailand is made up of a few hundred islands. In each reasonably-sized island there is an airport used by small aircraft. However, the transport system seems quite peculiar for visitors...

Ferry boats are very reliable. For instance, you can depart from Ko Khang Khao (เกาะคางคาว) and get to neighbouring islands for a reasonable price using ferry boats: Ko Sichang (เกาะสชง), Ko Kham Yai (เกาะขามใหญ), Ko Kham Noi (เกาะขามนอย), Ko Ram Dok Mai (เกาะรามดอกไม), Ko Prong (เกาะปรง)}, or Ko Yai Thao (เกาะใหญทาว) (Yes, Ko means island in Thai).

The airplane pilots, on the other hand, are very erratic. Once you pay the flight fare, the pilot will drop you off at a random island, each with the same probability, including the one you departed from. Even though the destination of the flight is random, the price is always K baht.

So when you want to go from one island to another you always have two options. Get a boat to a neighboring island, where the price varies according to the route, or get a flight.

The islands are numbered from 1 to N. Your task is to determine the minimum expected price of a trip from island 1 to N.

Input

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

The first line of each test case has 3 integers, N, M, and K, that represents the number of islands, the number of boats, and the cost of getting a flight, respectively.

The next M lines contain 3 integers each, A, B, C, indicating that there exists a boat trip that costs C baht to go from island A to B or from B to A. There exists at most one boat servicing each pair of islands.

Limits

  • 1 ≤ T ≤ 20
  • 1 ≤ N, M ≤ 105
  • 1 ≤ C ≤ 103
  • 1 ≤ K ≤ 103
Output

For each instance, print the minimum expected value of a trip from island 1 to island N. The error should not exceed 10 - 4.

Example
Input
2
3 3 1
1 2 10
1 3 20
2 3 5
3 3 100
1 2 10
1 3 20
2 3 5
Output
3.0000000000
15.0000000000

E. Escape from Ayutthaya
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Ayutthaya was one of the first kingdoms in Thailand, spanning since its foundation in 1350 to its collapse in 1767. The organization of Extraordinary Mystery Investigators (IME, in their language) aims to uncover the secrets of this ancient kingdom. One of IME's most notorious historians is Márcio "the indispensable" Himura. He is currently researching the laws and punishments in place during King Ramathibodi I's rule. Recent discoveries suggest how Ramathibodi I used to punish the subjects that did not convert to Theravada Buddhism, the religion he adopted.

The punishment involved trapping the accused prisoner in a room with a single exit and to light up a fire. If the prisoner could manage to reach the exit before getting caught on fire, she or he was forgiven and allowed to live. Márcio has access to some records that describe the floorplans of the rooms where this punishment took place. However, there are no documents asserting whether the prisoners were forgiven. Márcio would like to know whether each of these prisoners had any chance at all of having been forgiven. For that, Márcio represented each room as a grid with N rows and M columns, where each position has a symbol with the following meaning

where "start" is the person's initial position in the room when fire has been lit up. Moreover, Márcio imposed the following constraints in his model:

  • Fire spreads in the four cardinal directions (N, S, E, O) at the speed of one cell per minute.
  • The prisoners can also move in these four directions at the same speed.
  • Neither fire nor the prisoners can walk through a wall.
  • If the prisoner and fire occupy the same position at any instant, the prisoner dies instantaneously.

You are a member of IME and Márcio would like to know if you deserve your position. He has charged you with the task of determining whether a prisoner had any chance to be forgiven.

Input

The first line has a single integer T, the number if test cases.

Each instance consists of several lines. The first line contains two integers, N and M. Each of the following N lines contains exactly M symbols representing, as described above, a room from which the prisoner must escape.

Limits

  • 1 ≤ T ≤ 100
  • The sum of the sizes of the matrices in all test cases will not exceed 2·106
  • 1 ≤ N ≤ 103
  • 1 ≤ M ≤ 103
Output

For each instance, print a single line containing a single character. Print Y if the prisoner had any chance of being forgiven; otherwise, print N.

Example
Input
3
4 5
....S
.....
.....
F...E
4 4
...S
....
....
F..E
3 4
###S
####
E..F
Output
Y
N
N

F. Fighting the Rajasi
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Muay Thai is a martial art originated in Thailand. Many of its practitioners became legends among Thai people. Among these legendary fighters, Nai Khanom Tom is considered the very best. Here's one of his famous anecdotes.

Burma's king Mangra made Nai Khanom Tom, who was a war prisoner, duel one of the finest Burmese fighters in order to judge their fighting styles. Nai Khanom Tom effortlessly beat his opponent. However, the referee claimed that Nai Khanom Tom only won because he performed Ram Muay, a ritualistic dance move. The king then ordered Nai to duel ten Burmese warriors, one after another. Nai Khanom Tom still beat them all. Having witnessed Nai's skills, king Mangra set him free.

This tale has been passed across generations. Some people even believe Nai Khanom Tom could beat any number of opponents, even mythic Thai creatures.

As a big Muay Thai fan, you want to verify this claim. Suppose Nai Khanom Tom has H hit points and has to duel against N Rajasis. Each of them has xi hit points and yi recovery points. To win a fight, Nai's hit points must be greater than the Rajasi's. After fighting, Nai loses xi hit points and recovers yi points afterwards. Moreover, Nai knows K spells that can instantly beat a Rajasi. However, when a spell is used, Nai does not lose nor wins hit points as in a usual fight.

Given the description of a set of N Rajasis, you must decide if Nai Khanom Tom can beat them all. Note that Nai Khanom Tom can choose to fight the Rajasis in any order he wants.

Input

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

For each test case, the first line contains three space-separated integers, N, H, and K, where H is Nai's initial hit points. Each of the following N lines have two space-separated integers, xi and yi.

Limits

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 2·103
  • 0 ≤ K ≤ N
  • The sum of N across all test cases will not exceed 2·104.
  • 0 ≤ H, xi, yi ≤ 109
Output

For each test case, print a single line with Y if it is possible for Nai Khanom Tom to beat all Rajasis; print N otherwise.

Example
Input
2
2 10 2
20 10
100 1
2 10 0
9 10
10 1
Output
Y
Y

G. Thai Lottery
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Borommarachathirat IV (สมเดจพระบรมราชาธราชท 4) was a ruler of the Ayutthaya Kingdom in the 16th century. Borommarachathirat IV decided to create a lottery for his subjects using dice. These are traditional Thai dice and they may have several faces, where each face is rolled with the same probability.

The ruler demands the lottery to be perfectly fair, that is, each of his subjects must have the same probability of winning. The lottery consists of a finite number of rounds of dice rolls and, after each round, it is either decided that there is a winner or that more rounds are required. The dice rolls must follows the following rules:

  • several dice may be rolled at the same round;
  • previous rounds may affect the choice of dice in the next rounds;
  • the same die can be rolled in multiple rounds.

It is imperative to ensure that each subject has the same chance of winning the lottery. Notice that this is not always possible. For instance, if there are 5 subjects and a single 6-face die, then it is impossible to have a fair lottery. On the other hand, with such a die one can have a fair lottery if the population size is 3, 6, 18, or 36 people, and so on.

Your task in this problem is to write a program to help the ruler decide if it is possible to have a fair lottery with the available dice.

Input

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

Each test case is given in two lines. The first line has 2 integer, N and K, the amount of people and dice, respectively. The second line has K integers, the i-th integer fi is the number of faces in the i-th die.

Limits

  • 1 ≤ T ≤ 120
  • 1 ≤ N ≤ 1018
  • 0 ≤ K ≤ 105
  • The sum of K over all test cases will not exceed 6·105
  • 1 ≤ fi ≤ 1018
Output

For each test case, print a single line containing a single character. Print Y if it is possible to make the lottery; otherwise, print N.

Example
Input
3
18 1
6
1 0

10 2
4 6
Output
Y
Y
N

H. Guarding the Temples
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

There are thousands of Buddhist temples in Thailand, known as "wat". Some of them, such as the "Wat Phra Kaew" in Bangkok's Grand Palace, are specially regarded for their importance and they're called royal temples. The "Wat Phra Kaew" is famous for housing the Emerald Buddha statue, a national treasure. In 2016, the ACM ICPC World Finals will take place in Phuket, Thailand, and so increased tourism is expected in this city. The authorities in Phuket thus want to improve security in its royal temples.

Phuket's Security Unit (PSU) hired the researcher Lua "the ingenious" Kuratowski. PSU needs to solve the following problem. Given N royal temples and M streets connecting them, they must position guards at these streets so that every royal temple can be under surveillance. They consider a temple as secured if there is a guard in at least one of the streets ending at the temple. Streets were laid out so that one can reach any temple from any other. Moreover, due to a cultural dislike of odd numbers, any time someone starts a walk at a temple and returns to it, the number of streets traversed is always even.

Lua knows you wish to advance to the World Finals next year, and she considers this to be a good test for your skills. She challenges you to find a solution with the minimum number of guards.

Input

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

Each test case spans several input lines. The first line has two integers, N and M, the number of royal temples and the number of streets joining temples, respectively. Each temple is represented by an integer between 1 and N. The next M lines describe the streets. Each street is represented by two integers, corresponding to the temples it joins.

Limits

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 103
  • 1 ≤ M ≤ 5·103
Output

For each instance, print a single line with the minimum number of guards needed to have all royal temples under surveillance.

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

I. The Kunming-Singapore Railway
time limit per test
3 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

The Kunming-Singapore Railway is a network of rail tracks (some already built, some under construction) connecting several Asian cities. The project started in 1900 with the goal to connect Kunming (China) to Singapore, through the British Empire. Afterwards, in 1918, the railway was connected to Thailand through rail track joining Bangkok and Singapore. In 2000, ASEAN (Association of Southeast Asian Nations) considered completing this railway system.

The project is scheduled for completion by 2020. Due to its importante for Southeast Asia integration, the contractors hired you to minimize the system maintenance cost. Given N cities that make up the Kunming-Singapore network, M initial rail tracks in the system and the Q tracks that will be built over time, you are required to compute the minimum cost do maintain the network connected after building each of these Q tracks. The system is initially connected if, for each pair of cities, there a set of tracks joining one to the other.

Input

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

Each test case spans several lines. The first line has three space-separated integers, N, M, and Q (described above). The next M lines describe the initial rail tracks, and the next Q lines describe the tracks to be added over time. Each track is represented as three space-separated integers, a, b, and c, where a and b represent the cities that are endpoints of the track, and c is the maintenance cost.

Limits

  • 1 ≤ T ≤ 8
  • 1 ≤ N, M, Q ≤ 3 × 104
  • The sum of all N, M and Q over all test cases will not exceed 3·105
  • 1 ≤ a, b ≤ N
  • 1 ≤ c ≤ 105
Output

For each test case, print Q lines. The ith line among these must have a single integer, the minimum maintenance cost after adding the ith track.

Example
Input
1
4 3 5
1 2 5
2 3 6
3 4 7
1 4 8
1 2 4
2 4 5
3 4 5
1 4 6
Output
18
17
15
14
14

J. The Kamphaeng Phet's Chedis
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A chedi (also known as stupa, dagoba, or pagoda) is a relic usually shaped as a conic tower built over the remains of someone Buddhists consider important. Some historical Thai sites have dozens such structures, dedicated to monks or nuns or other religious leaders (known as bhikkhu - ภกษณ, in Thailand). For instance, in Kamphaeng Phet some chedi inscriptions refer to Garuda (ครฑ), and similarly in Si Satchanalai and Sukhothai.

The differences between some Thai symbols are very subtle, making it hard for experts to analyze words. For instance, when any symbol of the word Ramakien (รามเกยรต) is changed, its meaning is altered completely. Since many of the sites are over 700 years old, the inscriptions are very worn.

An example is the pair of inscriptions below, found in distinct chedis:

จดษตงขนโดยพรภะบมพธานญาษ

จดตงขโกดยพระบรมษพทธานญาต

Experts believe both refer to the same entity. They developed a method to validate their hypothesis; this is called the method of minimum probabilistic difference.

The method works as follows. Let a = a1 a2... aN and b = b1 b2... bM be two inscriptions with N and M characters, respectively. The parameter called difference is initially set to zero. At each step, we analyze a pair (ai, bj) of characters with 1 ≤ i ≤ N + 1 and 1 ≤ j ≤ M + 1, starting with (a1, b1). Assume aN + 1 and bM + 1 are null characters.

During each step, there are four possible actions you can take:

  • Change the current pair to (ai + 1, bj + 1). This must be done iff i ≤ N, j ≤ M, and ai = bj.
  • Change the current pair to (ai + 1, bj) and increase the difference by 1. This can only be done if i ≤ N.
  • Change the current pair to (ai, bj + 1) and increase the difference by 1. This can only be done if j ≤ M.
  • Increase the difference by K and change the current pair to (ax, by). The values x and y are chosen randomly in the intervals [i + 1 . . N + 1] and [j + 1 . . M + 1], respectively. Each value in the interval has the same probability of being chosen. If i = N + 1, then i does not change. If j = M + 1, then j does not change.
The analysis ends after when the pair (aN + 1, bM + 1) is processed. Note that the difference parameter may vary with the choices made in the procedure.

The experts consider that, the smaller the computed difference, the higher correspondence between the inscriptions. They want you to write a program to compute the minimum expected difference between two inscriptions.

Input

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

Each test case starts with 3 integers N, M, and K, where N is the length of the first inscription and M is the length of the second inscription. The next two lines contain, respectively, the first and second inscription. An inscription is a string of characters from a to z.

Limits

  • 1 ≤ T ≤ 500
  • 1 ≤ N, M ≤ 3·103
  • The sum of N and M over all test cases will not exceed 1.2·104.
  • 0 ≤ K ≤ 105
Output

For each test case, print a real number, the minimum expected difference between two inscriptions. The error should not exceed 10 - 4.

Example
Input
3
3 3 2
aab
aba
4 3 0
abcc
eee
2 3 1
ab
cba
Output
2.0000000000
0.0000000000
1.9166666667

K. Training with Phuket's larvae
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Thai cuisine is known for combining seasonings so that every dish has flavors that are sweet (sugar, fruits, bell peppers), spicy, sour (vinegar, tamarind, lime), and salty (soy sauce, fish sauce). The most exotic dish, however, is the one containing fried insect larvae; naturally, it is often showcased to tourists. Westerners usually shudder at the thought of eating larvae, but they are highly valued in Thailand and they are a huge success in parties. Thai children often play with food. They specially like building triangles up using fried larvae as the edges.

Marcos "the (Rubik) solver" coaches his university's team on a famous computer programming contest. Next year, the contest's world finals will take place in Phuket, Thailand.

Marcos knows how Thai children like to play with larvae, so he had an idea for a special training session. His idea involves preparing a large amount of fried larvae of several different lengths. Each of his friends, in turn, must select three larvae to build a triangle. Then, the amount of fried larvae each friend has to eat is proportional to the area of the triangle she or he built.

Marcos hopes that, since you want to eat as little larvae as possible, you'll write a program to choose the larvae that forms a triangle of minimum area. Thus, besides training your computer programming skills, you'll also be training to face Thai cuisine. If you actually enjoy this dish, you may use this program to help your other friends, making sure that there will be more fried larvae left for you.

Input

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

Each test case starts with an integer N, the number of larvae. In the next line there are N space-separated real numbers a1, ..., an, representing the lengths of the larvae.

Limits

  • 1 ≤ T ≤ 30
  • 1 ≤ N ≤ 2·103
  • 1 ≤ ai ≤ 500
  • The sum of N over all test cases will not exceed 6·103
Output

For each test case, print a single line containing the minimum area for that case, the error should not exceed 10 - 4; if it is not possible to build a triangle from the larvae, print -1.

Example
Input
3
4
3 4 5 6
3
1 2 4
5
3.4 2.8 7.1 5.2 10
Output
5.3326822519
-1
4.3599885321

L. Putting plates on the tuk-tuks
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

The tuk-tuk (ตกตก), also known as "auto rickshaw," is a popular form of transportation in Thailand. In order to distinguish tuk-tuks from the other types of vehicles, the Phuket administration decided to create a new license plate system for them. Phuket's tuk-tuk fleet has been growing rapidly, mostly due to tourism, one of the most important economic activities in the province. The administration plans the new system to meet the demand for distinct license plates for the next 42 years.

A license plate system is defined by two numbers, C and D. A license plate in this system is a string formed by C consonants followed by D digits. A license plate cannot be empty (no consonant and no digit).

In the Thai alphabet there are 44 consonants and 10 digits. However, since the symbols of some consonants are too much alike, the administration decided to use only 26 consonants, whose symbols were considered sufficiently distinguishable.

To guarantee an appropriate supply of tuk-tuks for the contestants in the ICPC World Finals in 2016, Phuket's administration would like to know the number of distinct license plates it is possible to generate with a given license plate system.

Input

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

Each test case consists of a single line containing two integers C and D, the number of consonants and digits, respectively, in a license plate system.

Limits

  • 1 ≤ T ≤ 20
  • 0 ≤ C ≤ 6
  • 0 ≤ D ≤ 9
Output

For each test case, print a line with the amount of distinct license plates that can be generated by the corresponding system. The answer is guaranteed to be smaller than 231.

Example
Input
3
0 6
2 4
0 0
Output
1000000
6760000
0

M. Removing coins in Kem Kadrãn
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Andréh and his friend Andréas are board-game aficionados. They know many of their friends would love to go on a trip to Phuket, Thailand, and so they want to challenge them at Kem Kradãn, a traditional Thai board game.

Kem Kradãn (เกมกระดาน) has been played since the 2nd century AD. The game is played with N pieces where each piece has two faces, one of which is golden and the other is white. The game starts with all pieces arranged in a line on the board and they are numbered from 1 to N from left to right. When a piece numbered i has its golden face up, it can be removed from the board. When this is done, the pieces numbered i - 1 and i + 1 are flipped, if they're still there. The goal is to remove all game pieces.

Before challenging their friends, Andréh and Andréas want to make sure their initial configurations have a solution. To help them, given an initial configuration, you must determine if it is possible to remove all game pieces and, if so, you must show how to do it.

Input

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

Each test case is formed by a line containing an integer N, the number of pieces, followed by line containing a string of length N containing only the letters B (white face up) and D (golden face up), representing the initial state of the game.

Limits

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 105
  • The sum of N over all test cases will not exceed 5·105
Output

For each test case, print a line containing Y if it is possible to remove every piece from the board, or N otherwise. In case it is possible to remove all the pieces, you should also print on the next line a sequence of N integers each representing a piece number, indicating the order in which the pieces must be removed. If there is more than one possible sequence, you can print any of them.

Example
Input
4
3
BDB
5
DBDDB
5
DDBDD
6
DBBBBB
Output
Y
2 3 1
Y
4 5 1 2 3
N
Y
1 2 3 4 5 6