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

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

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

(1) An empty string is an SM string.

(2) If strings S1 and S2 are both SM strings, then S1S2 is an SM string.

(3) If a string S is an SM string, then {S}, [S], (S) and <S> are SM strings.

(4) If a string S is an SM string, then "sm"S is an SM string.

Given a string consisting of parentheses and "sm", determine if it is an SM string.

Input

The input consists of several lines.

Each line contains a string S (1 <= |S| <= 10^6 ), where S consists of only '{', '}', '[', ']', '(', ')', '<', '>' and "sm".

Testcases 1-2: without "sm".

Testcases 3-5: with "sm".

Output

For each string S, output "SM" if it is an SM string, "MS" if not.

There should be a '\n' in the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

下載後將副檔名改成zip（.cpp和.h為相同檔案，下載一個即可）

更改副檔名教學 : 

打開任意資料夾 >> 點擊上方 "檢視" >> 勾選 "副檔名" >> 將.cpp或.h更改成.zip

解壓縮 >> 點進 reference 目錄 >> 點進 en 目錄 >> Main_Page.html  就可以看到完整的cpprefernce.com離線版

===================================================================================================

Download the partial judge code and change the extension to .zip. (.cpp and .h is the same file. Donwload one of them is enough.)

Open the folder with the file in it >> click "view" >> check "File name extensions" >> change .cpp or .h to .zip
Unzip the file >> click "reference" > click "en" >> open "Main_Page.html". Then you can use the offline version of cppreference.com.

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

There are N licenses. Each license has a four-digit integer, where each digit is between 1 and 9. For example, if N=7, the input may look like

7

1324

5566

3578

4123

5656

4312

9847

We want to get the licenses that use the same digits and the digits should be sorted from small to large. For example, 1324, 4123, and 4312 are the combination of the same digits (1, 2, 3, and 4). We want to get 1234. Similarly, 5566 and 5656 are the combination of the same digits (5, 5, 6, and 6). We want to get 5566. 

For output, we list the modified licenses in an increasing order line by line, so the output will look 

1234

5566

Input

The first line contains a number N (1<=N<=100).

The next N lines provide the N four-digit integers.

Output

Each line shows a modified unique integer as explained in the problem description.

Remember to print a newline at the end of each line.

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 huuuuuuuuge 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. 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 a possible start position of Plankton.
5. 'O' means a portal. There may be many portals. Any 2 of the portals could reach each other within one step. A portal also could be reached in one step from 4 directions: up, down, left, and right.

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. Your task is to determine the start position of Plankton among all possible start positions and 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 '#', '.', '@', 'P', and 'O'.

Testcases 1-3: No portals and a single possible start position
Testcases 4-6: No portals
Testcases 7-8: No further constraints

Constraints:

• There are exactly one '@' on the map
• 5 <= n, m <= 1000
• There are no constraints on the numbers of possible start positions and portals, so be aware of time complexity.

Output

The first line contains an integer, specifying the minimum step count.
The second line contains two integers, a and b, which means the start position should be at the ath row and bth column. If there are more than one start position that has the minimum step count, print the upper one. If they are at the same row, print the left one.

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Note.

To improve the performance of I/O operations using cin / cout from the iostream, you can add the following lines of code to your program. Please note that after adding these lines, you should avoid using I/O functions in C such as printf / scanf.

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. Additionally, each guest at Hodilo has a membership level, and their 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 1. (fifth value = 0)

Notice for subtask 3. 

The fifth value in the arrival record of each guest indicates their willingness to share a table with others (0: not willing / 1: willing). Here's how we determine if a guest is able to share a table with others:

Select the tables that are currently occupied by other guests and have the fewest remaining seats, while also being able to accommodate the new guest.
If there are multiple tables with the same fewest remaining seats, choose the table where the earliest arrival time for all the guests at the same table is the earliest.
Make sure that these occupied guests are also willing to share a table with others.

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> <membership level> <table sharing willingness>
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 ≤ 2 × 10⁵, 1 ≤ M ≤ 10³
• Guests
  • 0 ≤ arrival timestamp ≤ 10⁹ (The given arrival time is in increasing order)
  • 1 ≤ group size ≤ max(table size)
  • 1 ≤ dining duration ≤ 10³
  • 0 ≤ membership level ≤ 5
  • table sharing willingness ∈ {0, 1}
• Tables
  • 1 ≤ table size ≤ 10³
  • 1 ≤ number of tables ≤ 10
• It's guaranteed that the answer will not exceed 10⁹

Subtasks

• Subtask 1 (50%)
  • membership level = 0
  • table sharing willingness = 0
• Subtask 2 (25%)
  • table sharing willingness = 0
• Subtask 3 (25%)
  • No additional constraints

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss