Cho một mảng số nguyên ~A_1, A_2, \cdots, A_N~, bạn sẽ phải xử lý ~Q~ truy vấn có dạng sau:

• ~1~ ~l~ ~r~ - Với mỗi phần tử ~i~ từ ~l~ đến ~r~, đặt ~A_i~ bằng tổng các chữ số của nó.
• ~2~ ~x~ - Ghi ra giá trị của ~A_x~.

Input

• Dòng đầu tiên ghi số nguyên dương ~N~ duy nhất (~1 \leq N \leq 2 \cdot 10^5~) là số phần tử của mảng ~A~.
• Dòng thứ hai ghi ~N~ số, số thứ ~i~ là phần tử ~A_i~ của mảng (~1 \leq A_i \leq 10^9~).
• Dòng thứ ba ghi số nguyên dương ~Q~ là số lượng truy vấn bạn cần xử lý (~1 \leq Q \leq 2 \cdot 10^5~).
• ~Q~ dòng tiếp theo mỗi dòng là một truy vấn có 1 trong 2 dạng sau:
  • ~1~ ~l~ ~r~ (~1 \leq l \leq r \leq N~).
  • ~2~ ~x~ (~1 \leq x \leq N~).

Output

Với mỗi truy vấn loại 2, ghi ra một số nguyên là đáp án cho truy vấn đó trên mỗi dòng.

Sample input

5
1 420 69 1434 2023
8
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5

Sample output

6
15
1434
1
6
7

Subtask

• ~30\%~ số test có ~1 \leq N, Q \leq 1000~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.