Description

A string is said to be valid if it matches one of the following rules:

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S1 and S2 are both valid, then S1S2 is valid.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 1000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

For case 1,2 : 1<N<100. 0<=length<100

For case 3,4 : 1<N<1000. 0<=length<1000

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Hurry! Hurry! Hurry! Wanted!!!

Rumor has it that students in NTHU and NCTU are very friendly. Whenever someone is looking for a Chinese tutor ( especially when that person is in a hurry ), students will recommend their classmates if they know their classmates are capable of being a nice Chinese tutor. Students will tag their classmates in a special format : "classmate_name the school_name pokemon_name"

For example, "王小明清大小鋸鱷" would be "Wangxiaoming the NTHU Waninoko" in English.

Since students in NTHU and NCTU are well educated, they will choose a suitable water type pokemon based on beginning rhymes. They organized a beginning rhymes list. Students can find what pokemon their classmates should be by checking the list. For classmates who can't find a suitable pokemon in the list, we say that they are not good at Chinese.

For example, since WangXiaoMing starts with "Wa", studnets will find a pokemon whose name starts with "Wa".

You want to recommend some of your classmates. Given the names of your classmates and the schools they study in. Please tag your classmates using the special format mentioned above.

Input

The first line contains a single integer n, meaning that you have n classmates to recommend.

The n following lines. Each consists of two strings : name of your classmate and the school he studies in.

It is guarenteed that ...

• lengths of your classmates' names and schools' names will be more than 1, less than 100.
• Every name of your classmates contains english alphabets only, starting with an upper-case character, followed by lower-case characters.

Output

For each of your classmates,

• If you can find a suitable pokemon based on the list, please output using the special format : "classmate_name the school_name pokemon_name" (without quotation mark)
• If you cannot find a suitable pokemon based on the list, please output "classmate_name is looking for a Chinese tutor, too!" (without quotation mark)

Each output occupies one line.

Notes for Sample IO

• Since "Tanner" doesn't start with "Tapu", so he isn't "Tanner the NCTU Tapu Fini"
• According to the list, names starting with "Pi" or "Pe" can be Pikachu, therefore "Peter" is "Peter the NCTU Pikachu"

Useless Hints

Why is Pikachu in the list? Go google search for "surfing pikachu" XDD.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are playing a game. The goal of this game is to kill the monster when you are still alive (HP > 0, HP = health point). The monster is dead if and only if its HP <= 0.

This game consists of rounds, and you go first in each round.

You have 3 options in each round:

1. ATTACK. This will deduct the monster's HP. If your damage point is p, then you can deduct p monster's HP.
2. HEAL. You can recover some of your HP, but it can't exceed your max HP.
3. Level-up. Level-up might enhance the effect of attacking or healing, but if you are not lucky enough, sometimes it will deduct the effect of attacking and healing. Thus, choosing to level-up is not always a good choice. If you have reached max level, taking this action makes no effect.

In each round, the monster will attack you once with a fixed amount of damage points.

You start the game with full HP and level 1. What is the minimun number of rounds you need to kill the monster?

Input

First line contains 4 numbers L, HP, MHP, MDMG.

• L = max level
• HP = your max HP
• MHP = monster's HP in the beginning of game
• MDMG = monster's damage point

Each of the next L lines describes each level, i-th line of them describing level i. Each of them consists of two numbers, DMG and HL.

• DMG = your damage point when you use ATTACK at level i
• HL = amount of HP you can recover when you use HEAL at level i

Limits:

• L <= 15
• HP <= 300
• MHP <= 400
• MDMG <= 10000
• DMG <= 10000
• HL <= 50

Output

Print a single integer, denoting the mininum number of steps you need to kill the monster.

If you are unable to beat the monster, print -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The goal of this problem is to transform the arrangement of tiles from the initial arrangement to a goal arrangement.

The legal moves are the moves in which the tiles adjacent to the empty tile are moved to either left, right, up, or down.

Your goal is to find the minimum move to solve the problem.

ouo.

hint

Using BFS/DFS to find answer may exceed memory limit and time limit of some test cases, so we recommend using A* algorithm,  which is more efficient. In A* algorithm, it determine the direction of searching by “steps until now + heuristic value”.

A* algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm

To improve heuristic function, you can adopt manhattan distance with Linear Conflict.

Manhattan distance: https://en.wikipedia.org/wiki/Taxicab_geometry

Linear Conflict: The tile set(t1, t2) is linear conflict if they have same goal row(column), and they are now in that row(column), but they are blocked by each other. A set of lenear conflict will cause at least two extra steps.

Input

Input contains 4 lines, each line has 4 numbers.

The given puzzle is guaranteed to contain numbers from 0 ~ 15.

The zero denotes the empty tile.

It is guaranteed that the given puzzle is solvable.

Output

Output the minimum move to solve the puzzle.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Again, Plankton is planning to steal Krabby Patty from Krusty Krab. This time he gives you a huuuuge amount of money and asks you to plan a great path for him to approach Krabby Patty.

You are given a map with some information. The map is a grid and contains a character on each cell, and Plankton cannot go out of the map since his legs are too short. Here are the meanings of each character:

1. '#' means the obstacle. This cell is blocked and cannot be reached.
2. '.' means road. This cell could be reached in one step from 4 directions: up, down, left, and right.
3. '@' means the Krabby Patty. There would only be one Krabby Patty on the map.
4. 'P' means the start position of Plankton.

Plankton's goal is to find the minimum step count between him and Krabby Patty, i.e. the length of the shortest path between Plankton and Krabby Patty. Plankton wants to know how long does it take to reach Krabby Patty, so your task is to output the minimum step count.

Input

The first line contains two integers, n and m, which means there are n rows and m columns for the map.
Each of the next n lines contains a string with length m. The strings would only contain '#', '.', '@', and 'P'.

Constraints:

• There are exactly one '@' on the map
• 5 <= n, m <= 1000

Output

There is only one line for output, which contains an integer, specifying the minimum step count.

If there is no way for plankton to reach Krabby Patty, print -1 instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Hodilo is a well-known hot pot restaurant, and it's extremely challenging to have a table during peak dining hours in Hodilo. Even though, the restaurant does not accept reservations in advance, requiring every guest to visit the restaurant, take a number, and wait for their turn. Hodilo is opening a new branch in Hsinchu, and you have been invited to design a queuing system, which helps assign a table to each guest. 

The provided data consists of the arrival record of each guest at the restaurant. Each guest's arrival time is unique. We will add them to the waiting list one by one and subsequently assign tables to the guests on the waiting list. Here's how we assign guests from the waiting list to tables:

• We will sort the waiting list based on the order in which guests arrive.
• Whenever a new guest arrives or some occupied tables are released, the following procedure is performed to see if any table assignment is possible:

Since we have access to the latest AI technology, we can accurately estimate the dining duration for each customer. By utilizing this information, we can determine the length of time each customer will occupy their table. As soon as a guest's dining time ends, we assume that the table can be cleared instantly, making it available immediately. 

Your task is to assist Hodilo in implementing this system and provide the estimated time when each customer can be seated at their table, allowing them to indulge in the delicious hot pot experience.

Please take a look at the following GIF demonstration for a better understanding of the sample I/O.

Input

The first line contains two integers N and M - the number of guests and the number of table types.

For each of the next N lines, the i-th line represents the i-th guest arrival at the restaurant. It’s given in the following format:
<arrival timestamp> <group size> <dining duration>
We use an integer to represent the timestamp. The timestamp of a guest being seated at a table plus their dining duration will determine when the table becomes available again.

Each of the next M lines represents the number of the tables for each size in the restaurant. It’s given in the following format:
<table size> <number of tables>

Output

Output N lines, where the i-th line shows the timestamp when the i-th guest can have their table.

Constraints

• 1 ≤ N ≤ 200000, 1 ≤ M ≤ 2
• Guests
  • 0 ≤ arrival timestamp ≤ 10⁹ (The given arrival time is in increasing order)
  • 1 ≤ group size ≤ max(table size)
  • 1 ≤ dining duration ≤ 120
• Tables
  • 1 ≤ table size ≤ 6
  • 1 ≤ number of tables ≤ 50
• It's guaranteed that the answer will not exceed 10⁹

Sample Input  Download

Sample Output  Download

Tags

Discuss