Chef and Science

All submissions for this problem are available.
Chef studied science at school. But now he was tired of it. He likes to solve problems on Codechef. Here and now, he decided to go to his favourite site and solve several interesting problems. But as it turned out Chef is not yet ready to solve the harder problems. So you have to help him.
If you take away all the foreword, then the task set is this: you have N nonnegative numbers A_{1}, A_{2} ... A_{N} and M requests. Each request consists of three numbers (l, v, k). MagicInteger(l,v) is equal to concatenation of the numbers A_{i}, such that (i = l + v * q & 1 <= i <= n & q >= 0). For each such request you have to write the kth digit of MagicInteger(l,v).
Concatanation example:
If you have 2 numbers 11, 22  after concatenation you will have 1122.
If you have 3 number 13, 44, 12  after concatenation you will have 134412.
One more example: 0, 3, 11, 0  after concatenation you will have 03110. First digit of this string is 0, not 3.
Input
The first line contains an integer N denoting the number of integers in the given array. The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the given array. The third line has a single integer M denoting the number of requests. The next M lines contains three space separated numbers in each line (l, v, k) denoting each request.
Output
For each request output a single line containing kth digit of MagicInteger(l, v). If the length of MagicInteger(l,v) is smaller than k, you need to output "So sad" without quotes.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ M ≤ 10^{5}
 0 ≤ A_{i} ≤ 10^{9}
 1 ≤ l, v ≤ 10^{5}
 1 ≤ k ≤ 10^{6}
Example
Input: 4 0 1 2 3 5 1 1 2 1 2 2 1 2 1 2 2 3 4 100000 1 Output: 1 2 0 So sad 3
Scoring
Subtask 1 (30 points): N ≤ 1000
Subtask 2 (25 points): V ≤ 100
Subtask 3 (45 points): Look at constraints
Author:  furko 
Editorial  http://discuss.codechef.com/problems/CHITHH 
Tags  binarysearch, furko, ltime04, medium, preprocessing 
Date Added:  15092013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 