You are at your grandparents' house and you are 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 is composed of $n$ rounds. For each $1\le i\le n$, the $i$-th round works as follows.

On the screen, a symbol $s_i$ appears, which is either ${+}$ (plus) or ${-}$ (minus). Then you must press one of the two buttons on the controller once. Suppose you press a button with the number $x$ written on it: your score will increase by $x$ if the symbol was ${+}$ and will decrease by $x$ if the symbol was ${-}$. After you press the button, the round ends.

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

Over the years, your grandparents bought many different controllers, so you have $q$ of them. The two buttons on the $j$-th controller have the numbers $a_j$ and $b_j$ written on them. For each controller, you must compute whether you can win the game playing with that controller.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of rounds.

The second line contains a string $s$ of length $n$ — where $s_i$ is the symbol that will appear on the screen in the $i$-th round. It is guaranteed that $s$ contains only the characters ${+}$ and ${-}$.

The third line contains an integer $q$ ($1 \le q \le 10^5$) — the number of controllers.

The following $q$ lines contain two integers $a_j$ and $b_j$ each ($1 \le a_j, b_j \le 10^9$) — the numbers on the buttons of controller $j$.


-----Output-----

Output $q$ lines. On line $j$ print ${YES}$ if the game is winnable using controller $j$, otherwise print ${NO}$.


-----Examples-----

Input
8
+-+---+-
5
2 1
10 3
7 9
10 10
5 3
Output
YES
NO
NO
NO
YES
Input
6
+-++--
2
9 7
1 1
Output
YES
YES
Input
20
+-----+--+--------+-
2
1000000000 99999997
250000000 1000000000
Output
NO
YES


-----Note-----

In the first sample, one possible way to get score $0$ using the first controller is by pressing the button with numnber $1$ in rounds $1$, $2$, $4$, $5$, $6$ and $8$, and pressing the button with number $2$ in rounds $3$ and $7$. It is possible to show that there is no way to get a score of $0$ using the second controller.

Difficulty: MEDIUM
Tags: Sorting

Mathematics
Skill types: Sorting

Starter code:

Solutions:
n = int(input())
res = []
plus = 0
minus = 0
rounds = []
s = input()
q = int(input())
while q > 0:
	x = input().split(' ')
	(first, second) = (int(x[0]), int(x[1]))
	rounds.append(sorted([first, second]))
	q -= 1
for i in range(len(s)):
	if s[i] == '+':
		plus += 1
	if s[i] == '-':
		minus += 1
(max1, min1) = (max(plus, minus), min(plus, minus))
for (min2, max2) in rounds:
	if max1 == min1:
		res.append('YES')
		continue
	if max2 == min2:
		if max1 == min1:
			res.append('YES')
		else:
			res.append('NO')
		continue
	c = max2 * min1 - max1 * min2
	cur = c / (max2 - min2)
	if cur - int(cur) == 0 and cur >= 0:
		res.append('YES')
	else:
		res.append('NO')
for x in res:
	print(x)


n = int(input())
s = input()
q = int(input())
np = s.count('+')
nm = s.count('-')
for _ in range(q):
	(a, b) = map(int, input().split())
	numerator = (nm - np) * b
	denominator = a - b
	if a == b:
		r = np == nm
	elif numerator % denominator != 0:
		r = False
	else:
		r = -nm <= numerator // denominator <= np
	print('YES' if r else 'NO')


def fun(num_plus, num_minus, a, b):
	if a == b:
		return 'YES' if num_plus == num_minus else 'NO'
	else:
		r = a * (num_minus - num_plus) % (a - b)
		if r == 0:
			k = a * (num_minus - num_plus) // (a - b)
			return 'YES' if k in range(-num_plus, num_minus + 1) else 'NO'
		else:
			return 'NO'
n = int(input())
s = input()
q = int(input())
num_plus = sum([1 for i in s if i == '+'])
num_minus = n - num_plus
for i in range(q):
	(a, b) = map(int, input().split())
	print(fun(num_plus, num_minus, a, b))


n = int(input())
s = input()
m = s.count('-')
p = s.count('+')
(m, p) = (max(m, p), min(m, p))
q = int(input())
for i in range(q):
	(t1, t2) = (m, p)
	(b1, b2) = map(int, input().split())
	(b1, b2) = (min(b1, b2), max(b1, b2))
	r = b1 * t1 - b2 * t2
	t = 0
	if r < 0:
		if -r % (b2 - b1) == 0 and -r // (b2 - b1) <= t2:
			r = 0
	if r == 0:
		print('YES')
	else:
		print('NO')


n = int(input())
s = input()
pl = s.count('+')
mn = s.count('-')
m = int(input())
for __ in range(m):
	(a, b) = map(int, input().split())
	abmax = max(a, b)
	abmin = min(a, b)
	if pl == mn:
		print('YES')
		continue
	if pl < mn:
		smax = pl * abmax - mn * abmin
		diff_plus = abmax - abmin
		if not diff_plus:
			print('NO')
			continue
		if smax < 0:
			print('NO')
			continue
		if smax == 0:
			print('YES')
			continue
		if smax % diff_plus or smax < diff_plus:
			print('NO')
			continue
		if smax // diff_plus <= n:
			print('YES')
			continue
	else:
		smax = pl * abmin - mn * abmax
		diff_plus = abmin - abmax
		if not diff_plus:
			print('NO')
			continue
		if smax > 0:
			print('NO')
			continue
		if smax == 0:
			print('YES')
			continue
		smax = abs(smax)
		diff_plus = abs(diff_plus)
		if smax % diff_plus or smax < diff_plus:
			print('NO')
			continue
		if smax // diff_plus <= n:
			print('YES')
			continue


(n, s, t, pos, neg) = (int(input()), input(), int(input()), 0, 0)
for x in s:
	if x == '+':
		pos += 1
	else:
		neg += 1
for i in range(t):
	(c, p) = map(int, input().split())
	(x, y) = (min(c, p), max(c, p))
	(high, low) = (y * pos - x * neg, x * pos - y * neg)
	if low > 0 or high < 0:
		print('NO')
	elif low == 0 or high == 0:
		print('YES')
	elif y - x == 0:
		print('NO')
	elif high % (y - x) == 0:
		print('YES')
	else:
		print('NO')


from collections import Counter
n = int(input())
s = str(input())
cnt = Counter(s)
p = cnt['+']
m = cnt['-']
q = int(input())
for i in range(0, q):
	(a, b) = map(int, input().split())
	if p == m:
		print('YES')
		continue
	if a == b:
		print('NO')
		continue
	if a < b:
		(a, b) = (b, a)
	if p * a - m * b == 0:
		print('YES')
		continue
	if (p * a - m * b) % (a - b) == 0 and (p * a - m * b) / (a - b) <= n and ((p * a - m * b) / (a - b) >= 0):
		print('YES')
	else:
		print('NO')