You are given a string s whose length is n. And s consists of only numbers except 0.
In this problem si represents the i-th character in s and s is 0 based indexing. And we call a substring s[l...r) of s is a string sl sl+1 sl+2 ... sr-1 (i.e. the concatenation of sl, sl+1, sl+2, ..., sr-1 in the order).
Now you have to execute the folloing operation on s for q times.
In each operation, you are given three numbers a, b and sz. And then:
For example suppose s = "3124561245" whose length is n = 10. And q = 2.
In the first operation, consider a = 0, b = 1 and sz = 1. So A = s[a,a+sz) = s[0,1) = "3" and B = "1". s will become "24561245" after removing A and B from it. Afterwards we output the product of A x B = 3 x 1 = 3.
In the second operation, consider a = 1, b = 4 and sz = 2. So A = "45" and B = "12". s will become "2645" after removing A and B from it. Finally we output the product of A x B = 45 x 12 = 540.
The first line contains an integer n (1 ≤ n ≤ 1000) – the length of s.
Next line contains the string s (|s| = n) which consists of only numbers except 0.
The third line contains one integer q (1 ≤ q ≤ 1000) – the times you have to execute operation on s.
Then q lines follow. Each line contains three integers a, b, sz (1 ≤ sz ≤ 9, 0 ≤ a < a+sz ≤ b < b+sz ≤ |s|) – the range of the two substring A and B.
It is guaranteed that all the operations are valid. That is you can always remove A and B from s successfully.
For each operation you execute on s, output the product of A x B.
And print a newline('\n') at the end of each line.