## BestCoder Round #57(Div.2) (2/4) (Div.1) (1/4)

maksyuki 发表于 比赛 分类，标签:

# Scaena Felix

Problem Description

Given a parentheses sequence consist of '(' and ')', a modify can filp a parentheses, changing '(' to ')' or ')' to '('.

If we want every not empty <b>substring</b> of this parentheses sequence not to be "paren-matching", how many times at least to modify this parentheses sequence?

For example, "()","(())","()()" are "paren-matching" strings, but "((", ")(", "((()" are not.

Input

The first line of the input is a integer T, meaning that there are T test cases.

Every test cases contains a parentheses sequence S only consists of '(' and ')'.

1≤|S|≤1,000.

Output

For every test case output the least number of modification.

Sample Input

3

()

((((

(())

Sample Output

102

Source

BestCoder Round #57 (div.2)

# B Conturbatio

Problem Description

There are many rook on a chessboard, a rook can attack the row and column it belongs, including its own place.

There are also many queries, each query gives a rectangle on the chess board, and asks whether every grid in the rectangle will be attacked by any rook?

Input

The first line of the input is a integer T, meaning that there are T test cases.

Every test cases begin with four integers n,m,K,Q.
K is the number of Rook, Q is the number of queries.

Then K lines follow, each contain two integers x,y describing the coordinate of Rook.

Then Q lines follow, each contain four integers x1,y1,x2,y2 describing the left-down and right-up coordinates of query.

1≤n,m,K,Q≤100,000.

1≤x≤n,1≤y≤m.

1≤x1≤x2≤n,1≤y1≤y2≤m.

Output

For every query output "Yes" or "No" as mentioned above.

Sample Input

22 2 1 21 11 1 1 22 1 2 22 2 2 11 11 22 1 2 2

Sample Output

Yes

No

Yes

HintHuge input, scanf recommended.

Source

BestCoder Round #57 (div.2)