Tổng chữ số chia dư

Cho hai số nguyên dương a và b. Nhiệm vụ của bạn là tính tổng tất cả các chữ số của các số từ a đến b, sau đó in ra phần dư khi chia tổng này cho 9.

Ví dụ: Với a = 12, b = 14, các số là 12, 13, 14. Tổng chữ số là 1+2 + 1+3 + 1+4 = 12. Kết quả là 12 % 9 = 3.

Input

• Một dòng duy nhất chứa hai số nguyên a và b \((1 \le a \le b \le 10^{18})\).

Output

• Một dòng duy nhất là phần dư khi chia tổng chữ số từ a đến b cho 9.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(b \le 10^5\)
• Subtask \(2\) (\(30\%\) số điểm): \(b \le 10^{12}\)
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm

Example

12 14

3

1 9

0

Tại một hội chợ, có một trò chơi như sau:

• Cho một xâu ký tự S chỉ gồm các chữ cái tiếng Anh in thường.
• Một thao tác là đưa ký tự đầu tiên của xâu xuống cuối xâu.
  Ví dụ: xâu banana sau một thao tác trở thành ananab; thao tác tiếp theo sẽ thành nanaba.

Người chơi thực hiện tổng cộng K lượt chơi, trong lượt chơi thứ i sẽ thực hiện đúng i thao tác lên xâu hiện tại. Sau khi hoàn thành K lượt, hãy cho biết ký tự ở vị trí thứ X trong xâu cuối cùng là gì.

Input

• Dòng đầu tiên chứa xâu S \((1 \le |S| \le 10^6)\).
• Dòng thứ hai chứa số nguyên \(K\) \((1 \le K \le 10^{18})\).
• Dòng thứ ba chứa số nguyên \(X\) \((1 \le X \le |S|)\).

Output

• Một ký tự duy nhất là ký tự ở vị trí thứ X trong xâu sau khi thực hiện toàn bộ K lượt chơi.

Scoring

• Có \(60\%\) số test trong \(60\%\) số điểm có \(|S| \le 10^5\), \(K \le 10\).
• Có \(20\%\) số test trong \(60\%\) số điểm có \(K \le 10^9\).
• \(20\%\) số test còn lại không có ràng buộc gì thêm.

Example

banana
4
3

b

Giả sử bạn có một dãy số tự nhiên được tạo ra bằng cách liệt kê tất cả các số chỉ chứa chữ số lẻ (1, 3, 5, 7, 9) theo thứ tự tăng dần. Dãy này bắt đầu như sau:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, 33, 35, 37, 39, ...

Nếu nối tất cả các số lại thành một xâu liên tiếp, ta được:

1357911131517193133353739...

Nhiệm vụ của bạn là: cho trước số nguyên k, hãy tìm chữ số thứ k trong xâu vô hạn trên.

Input

• Một dòng duy nhất chứa số nguyên k \((1 \le k \le 10^{16})\).

Output

• Một chữ số duy nhất là chữ số ở vị trí thứ k trong dãy số lẻ liên tiếp.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(k \le 10^5\)
• Subtask \(2\) (\(30\%\) số điểm): \(k \le 10^7\)
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm

Example

5

9

14

1

Marisa muốn nấu ăn bằng một số loại thảo mộc cô mới hái được. Mỗi loại có một độ độc nhất định, tuy vậy nếu kết hợp các loại thảo mộc mà tích độ độc của chúng bằng bội chung nhỏ nhất của chúng thì độc tố sẽ biến mất.

Có \(q\) ngày, ngày thứ \(q\) Marisa muốn chọn các loại thảo mộc từ vị trí \(l\) đến vị trí \(r\) để nấu ăn, mỗi món ăn sẽ được nấu từ các thảo mộc liên tiếp và phải không có độc. Hãy giúp cô tính số lượng món ăn ít nhất có thể nấu được vì nhiều quá cô sẽ không ăn hết.

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(n, q\).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_i\) là độ độc của món ăn thứ \(i\).
• \(q\) dòng tiếp theo gồm 2 số \(l_i, r_i\) .

Output:

• Gồm \(q\) số nguyên dương là đáp án của \(q\) ngày.

Sample Test:

Input

5 2
2 3 10 7 5
2 4
3 5

Output:

1
2

Giải thích:

• Ở test 1, 3 số 3 10 7 có tích bằng với bội chung nhỏ nhất là 210 nên có thể chia thành 1 đoạn.
• Ở test 2, có thể chia thành đoạn 10 và 7 5, không thể có kết quả nhỏ hơn.

Giới hạn:

• Trong mọi test \(a_i \le 10^5\).
• 25% số điểm: \(n, q \le 100\).
• 25% số điểm: \(n, q \le 1000\).
• 25% số điểm: \(a_i\) là các số nguyên tố.
• 25% số điểm: \(n, q \le 10^5\).

Cho một mảng số nguyên a gồm N phần tử. Ta định nghĩa điểm của một đoạn con liên tiếp là tổng của giá trị lớn nhất và giá trị nhỏ nhất trong đoạn đó.

Yêu cầu: chia mảng thành đúng K đoạn liên tiếp không giao nhau, không rỗng, sao cho tổng điểm của tất cả các đoạn là lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên N, K \((1 \le N \le 10^5,\ 1 \le K \le \min(N, 20))\) — số phần tử của mảng và số đoạn cần chia.
• Dòng thứ hai gồm N số nguyên a_1, a_2, ..., a_n \((0 \le a_i \le 10^9)\) — các giá trị trong mảng.

Output

• Một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được sau khi chia mảng thành K đoạn liên tiếp.

Scoring

Example

5 3
3 5 2 3 4

22

3 2
10 6 2006

4028

Dino vừa được mẹ mua tặng một bộ đồ chơi có thể biến đổi các xâu nhị phân. Bộ đồ chơi gồm m vị trí, mỗi vị trí i mang một giá trị a_i.

Khi một xâu nhị phân s độ dài n được đưa vào vị trí i, bộ đồ chơi sẽ thực hiện phép biến đổi như sau:

• Áp dụng phép dịch vòng phải >> a_i lên s, tạo ra s >> a_i.
• Sau đó thực hiện phép XOR giữa s và s >> a_i:
  \(\(s' = s \oplus (s >> a_i)\)\)
  (Ở đây, >> là phép cyclic right shift, ⊕ là phép XOR).

Ví dụ: abcde >> 2 = deabc.

Dino rủ được q người bạn cùng thử bộ đồ chơi. Mỗi người bạn mang theo một xâu nhị phân x_i độ dài n, và muốn thực hiện biến đổi liên tiếp từ vị trí l_i đến r_i. Hãy giúp họ tính toán kết quả cuối cùng sau loạt biến đổi.

Input

• Dòng đầu tiên chứa ba số nguyên n, m, q \((1 \le n \le 16,\ 1 \le m \le 10^4,\ 1 \le q \le 10^6)\) — độ dài xâu, số vị trí trên đồ chơi, và số lượt bạn bè chơi.
• Dòng thứ hai gồm m số nguyên a_1, a_2, ..., a_m \((0 \le a_i < n)\) — giá trị tại mỗi vị trí.
• q dòng tiếp theo, mỗi dòng gồm ba số nguyên x_i, l_i, r_i:
• x_i là một số nguyên không âm biểu diễn xâu nhị phân có n bit.
• \((0 \le x_i < 2^n,\ 1 \le l_i \le r_i \le m)\).

Output

• Gồm q dòng, mỗi dòng là một số nguyên không âm có n bit — kết quả cuối cùng của xâu sau các phép biến đổi.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10\), \(m \le 1000\), \(q \le 1000\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10\), \(m \le 1000\), \(q \le 10^5\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 16\), \(m \le 10^4\), \(q \le 10^5\)
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm

Example

4 3 3
2 1 3
3 1 1
5 1 2
7 1 3

15
0
0