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

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

There’s a numberline. Initially, no point is lying on it.
Given N queries, each is one of the following two types:
1 x: Add a point x on the numberline. If x is already lying on the numberline, remove it instead.

2 x: There are a lot of segments, separated by the points on the numberline. You have to answer the length of the segments that x is lying on. If x is the endpoints of two segments, x is considered lying on the right one. Furthermore, if the length of the segment is infinite, output −1.

Constraints

• 1 ≤ N ≤ 100000
• 1 ≤ x ≤ 1000000000

Input

The first line contains a integer N represents the number of queries.
In the following N lines, each contains two integers, represents the query.

Output

For each query of type 2, outputs its answer line by line.

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

Description

In this world, everyone needs to work to earn money to survive.

Jobs are provided by armored men (盔甲人), and little cutes (小可愛) will try to get the jobs they want.

After working, the armored men will calculate the day's salary for each little cute.

To efficiently pay salaries to little cutes, the armored men need to track which job is chosen by which little cute. Therefore, they decided to write a program to assist them.

There are N jobs, numbered from 1 to N, and each job has a type t_i (1 ≤ i ≤ N). There are M little cutes lined up for the jobs. Each little cute wants to apply for k_j (1 ≤ j ≤ M) jobs, and once a little cute gets all his jobs, he will leave the queue; otherwise, he will stay in the queue and cry, and at last the little cute and those behind him all can't get the jobs.

Note that when choosing a job, among jobs of this type, a little cute will choose the job with the smallest job_id (1 ≤ job_id ≤ N). Each job can only be chosen once.

For each job, you should output the little_cute_id (1 ≤ little_cute_id ≤ M) of the little cute who has taken it, or 0 if nobody does.

Constraints

• 1 ≤ N, M ≤ 10⁶
• 1 ≤ ti ≤ 10⁹
• ∑kj≤10⁶

Subtasks

1. (2/6) 1 ≤ M ≤ 100, 1 ≤ N ≤ 100          
2. (2/6) 1 ≤ M ≤ 1000, 1 ≤ N ≤ 10000 
3. (2/6) No additional constraints             

Input

The first line of input contains two positive integers M, N, as described in the statement.
Next, there would be M job sets, each represented by two lines: 1) the first line contains a single positive integer kj, denoting the size of the j_th little cute's job set; 2) the second line contains kj integers, each denoting one of the job types in this job set.

Finally, there would be N integers, t₁∼ t_N, as the statement describes.

Output

Output N lines, each containing a single integer, indicating which little cute has taken the corresponding job.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given \(N\) integers \(a_1 \dots a_N\) and \(M\) queries.
In each query, you will be given one integer \(x\), please output an integer in \(a\) which is closest to \(x\).
If there are more than one such integer, please output the smaller one.

ps. We suggest you use std::set to do this problem :)

Input

The first line contains two integers \(N, M\).
The second line contains \(N\) integers \(a_1, a_2 \dots a_N\)
Each of the next \(M\) lines contains an integer \(x\).

\(N \quad M\)
\(a_1 \quad a_2 \dots a_N\)
\(x_1\)
\(\vdots\)
\(x_M\)

Constraints

• \(1 \le N, M \le 10^5\)
  
• \(0 \le a_i, x_i \le 10^9\)

Output

Please output the answer of each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss