Controllers

Time limit2sMemory limit1024 MB

Summary

Given a string of + and - round symbols, decide for each pair of button values whether pressing one button per round can bring the final score to exactly 0.

Level: Medium4 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

You are at your grandparents' house and playing an old video game on a strange console. Your controller has only two buttons, and each button has a number written on it.

Initially, your score is $0$ . The game has $n$ rounds. For each $1 ≤ i ≤ n$ , round $i$ works as follows.

A symbol $s_i$ appears on the screen. It is either + or -. Then you must press one of the two buttons exactly once. If you press a button with the number $x$ written on it, your score increases by $x$ when the symbol is +, and decreases by $x$ when the symbol is -. The round ends after you press the button.

After all $n$ rounds, you win if your score is $0$ .

Your grandparents have bought many different controllers over the years, so there are $q$ of them. The two buttons on the $j$ -th controller have the numbers $a_j$ and $b_j$ . For each controller, determine whether you can win the game with it.

Input

The first line contains an integer $n$ ( $1 ≤ n ≤ 2 \cdot 10^5$ ), the number of rounds.

The second line contains a string $s$ of length $n$ , where $s_i$ is the symbol shown in round $i$ . $s$ contains only the characters + and -.

The third line contains an integer $q$ ( $1 ≤ q ≤ 10^5$ ), the number of controllers.

Each of the next $q$ lines contains two integers $a_j$ and $b_j$ ( $1 ≤ a_j, b_j ≤ 10^9$ ).

Output

Print $q$ lines. On line $j$ , print YES if you can win the game with the $j$ -th controller, and NO otherwise.

Examples3

Example 1

Input

8
+-+---+-
5
2 1
10 3
7 9
10 10
5 3

Expected output

YES
NO
NO
NO
YES

Example 2
Input
```
6
+-++--
2
9 7
1 1
```
Expected output
```
YES
YES
```

Example 3

Input

20
+-----+--+--------+-
2
1000000000 99999997
250000000 1000000000

Expected output

NO
YES