sameers-subarray-sum

Sameer loves to play with subarrays. He has a array of digits(0-9).  A subarray is called a sameer subarray if the subarray is a multiple of 9.
Now for each given subarray, you should find whether the subarray is a Sameer subarray or not.

Input format:
The first line has N, the number of digits of array. (1 ≤ N ≤ 100000)
The next line has the n digits 
The next line has Q, the number of queries,  (1 ≤ Q ≤ 100000).
The next Q lines contains two integers L and R, the leftmost and rightmost elements of subarray.

Output format:
Output has Q lines for each of the query.
If the subarray for the ith query  is a sameer subarray, then print "SAMEER" (without quotes). Else print "NO" (without quotes)

Setter : Ashsish Chauhan

SAMPLE INPUT
5
12345
5
2 4
1 3
1 5
2 3
4 5

SAMPLE OUTPUT
SAMEER
NO
NO
NO
SAMEER

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: