CODE FESTIVAL 2017 Final (Parallel) - Combination Lock

Ringo has a string S.

He can perform the following N kinds of operations any number of times in any order.

* Operation i: For each of the characters from the L_i-th through the R_i-th characters in S, replace it with its succeeding letter in the English alphabet. (That is, replace `a` with `b`, replace `b` with `c` and so on.) For `z`, we assume that its succeeding letter is `a`.



Ringo loves palindromes and wants to turn S into a palindrome. Determine whether this is possible.

Constraints

* 1 \leq |S| \leq 10^5
* S consists of lowercase English letters.
* 1 \leq N \leq 10^5
* 1 \leq L_i \leq R_i \leq |S|

Input

Input is given from Standard Input in the following format:


S
N
L_1 R_1
L_2 R_2
:
L_N R_N


Output

Print `YES` if it is possible to turn S into a palindrome; print `NO` if it is impossible.

Examples

Input

bixzja
2
2 3
3 6


Output

YES


Input

abc
1
2 2


Output

NO


Input

cassert
4
1 2
3 4
1 1
2 2


Output

YES

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
from operator import sub
sys.setrecursionlimit(100000)

def dfs(s, visited):
	visited.add(s)
	for v in links[s]:
		if v not in visited:
			dfs(v, visited)

def solve():
	checked = set()
	for i in range(ls // 2 + 1):
		if i in checked:
			continue
		visited = set()
		dfs(i, visited)
		inner_total = sum((sd[k] for k in visited)) % 26
		if inner_total != 0:
			return False
		checked.update(visited)
	return True
s = input()
sl = list(map(ord, s))
sd = list(map(sub, sl + [97], [97] + sl))
ls = len(s)
lsd = len(sd)
n = int(input())
links = [set() for _ in range(lsd)]
for i in range((ls + 1) // 2):
	links[i].add(ls - i)
	links[ls - i].add(i)
for (a, b) in (map(int, input().split()) for _ in range(n)):
	links[a - 1].add(b)
	links[b].add(a - 1)
print('YES' if solve() else 'NO')