CF1189C Candies!

Consider a sequence of digits of length $ 2^k $ $ [a_1, a_2, \ldots, a_{2^k}] $ . We perform the following operation with it: replace pairs $ (a_{2i+1}, a_{2i+2}) $ with $ (a_{2i+1} + a_{2i+2})\bmod 10 $ for $ 0\le i

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the sequence. The second line contains $ n $ digits $ s_1, s_2, \ldots, s_n $ ( $ 0 \le s_i \le 9 $ ). The third line contains a single integer $ q $ ( $ 1 \le q \le 10^5 $ ) — the number of queries. Each of the next $ q $ lines contains two integers $ l_i $ , $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — $ i $ -th query. It is guaranteed that $ r_i-l_i+1 $ is a nonnegative integer power of $ 2 $ .

Output $ q $ lines, in $ i $ -th line output single integer — $ f([s_{l_i}, s_{l_i + 1}, \ldots, s_{r_i}]) $ , answer to the $ i $ -th query.

The first example illustrates an example from the statement. $ f([7, 3, 1, 7]) = 1 $ : sequence of operations is $ [7, 3, 1, 7] \to [(7 + 3)\bmod 10, (1 + 7)\bmod 10] $ $ = $ $ [0, 8] $ and one candy as $ 7 + 3 \ge 10 $ $ \to $ $ [(0 + 8) \bmod 10] $ $ = $ $ [8] $ , so we get only $ 1 $ candy. $ f([9]) = 0 $ as we don't perform operations with it.