Alina and the Mountains#12241
Sign in

Alina and the Mountains

2 seconds
256 megabytes
Very hard

During a hike in the mountains, Alina found a string consisting of digits from to . Over the next days, she planned to climb smaller mountains and find substrings of this string from L_i to R_i.

To descend, she needed to pass by Tanya, who guarded the only exit from the mountains. Tanya liked the function f(t, A, B), which returns if any digit in the string differs from or ; otherwise, it returns the number formed by concatenating all the digits in the string (for the string "", A=1, B=3, the function returns ). There is also a function g(t, A, B) = \sum_{i = 1}^{|t|} \sum_{j = i}^{|t|} f(t[i \ldots j], A, B).

To leave the mountain on the -th day, Alina must find g(s[L_i \ldots R_i], A_i, B_i) for the given substring from L_i to R_i. Since this number can be quite large, it should be output modulo . Help Alina with this.

Note. t[i \ldots j] \;=\; t_i t_{i+1} \dots t_j, that is, the substring of the string that starts at position and ends at position inclusive.

Input

The first line contains the string (1 \le |s| \le 3 \cdot 10^{5}), consisting of digits from to . The second line contains one integer (1 \le q \le 3 \cdot 10^{5}) — the number of days Alina climbed smaller mountains. The next lines contain L_i, R_i, A_i, B_i (1 \le L_i \le R_i \le |s|, 1 \le A_i \le B_i \le 9).

Output

For each day, output g(s[L_i \ldots R_i], A_i, B_i) on a separate line.

Examples

Example 1

Loading
Loading

Note

For the first query L=6, R=9, A=1, B=2: of any substring will be , so their sum will also be .

For the fifth query: t="2443", A=1, B=4. g(t,1,4)=f(2,1,4)+f(24,1,4)+f(244,1,4)+f(2443,1,4) +f(4,1,4)+f(44,1,4)+f(443,1,4) +f(4,1,4)+f(43,1,4)+f(3,1,4) =0+0+0+0+4+44+0+4=52

Scoring

  1. Subtask ( points): (n \le 5000, q=1)

  2. Subtask ( points): (q=1)

  3. Subtask ( points): (R_i=n)

  4. Subtask ( points): (q,n \le 100)

  5. Subtask ( points): (n \le 100)

  6. Subtask ( points): (n \le 500, A_i=1, B_i=7)

  7. Subtask ( points): (n \le 200)

  8. Subtask ( points): (n \le 8000, A_i=1, B_i=7)

  9. Subtask ( points): (n \le 2000)

  10. Subtask ( points): (s=11 \ldots 1, A_i=B_i=1,n \le 5000)

  11. Subtask ( points): (s=11 \ldots 1, A_i=B_i=1)

  12. Subtask ( points): (A_i=1, B_i=7)

  13. Subtask ( points): (n \le 50000)

  14. Subtask ( points): No additional constraints