Thầy Đ là một thầy giáo giàu có thuộc trường chuyên L giấu tên. Thầy hiện là chủ sở hữu của rất nhiều mảnh đất đắt giá ở Hòa Xuân. Một trong số đó có diện tích \(n\times m\) mét vuông. Thầy Đ đang muốn lấp đầy mảnh đất của mình bằng các chiếc máy phát điện với diện tích \(1\times2\), \(2\times1\) hoặc \(1\times1\). Vì những chiếc máy \(1\times1\) có công suất kém hơn nên thầy đang muốn ưu tiên sử dụng hai loại máy còn lại. Hãy giúp thầy Đ tìm cách lấp đầy mảnh đất trên bằng ít máy loại \(1\times1\) nhất.

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương \(n, m\) (\(1 \leq n, m \leq 10^{18}\))

Output

• Một dòng duy nhất chứa số nguyên là đáp án của bài toán

Scoring

• Subtask \(1\) (\(40\%\)): \(n,m\leq20\)
• Subtask \(2\) (\(30\%\)): \(n,m\leq10^9\)
• Subtask \(3\) (\(30\%\)): \(n,m\leq10^{18}\)

Example

2 4

0

6 3

0

Cho xâu \(S\) gồm các chữ số. Hãy đếm số lượng xâu con \([l \dots r]\) sao cho tạo thành một số tự nhiên chia hết cho \(3\) (không có số \(0\) đứng đầu)

Dấu hiệu chia hết cho \(3\): Một số chia hết cho \(3\) khi tổng các chữ số của số đó chia hết cho \(3\). Ví dụ: \(354\) chia hết cho \(3\) vì \(3 + 5 + 4 = 12\) chia hết cho \(3\).

Input

• Gồm dòng duy nhất chứa xâu \(S\) \((|S| \leq 10^5)\).

Output

• Gồm một số nguyên duy nhất là số xâu con thỏa mãn.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(|S| \leq 5000\)
• Subtask \(2\) (\(50\%\) số điểm): \(|S| \leq 10^{5}\)

Example

363

6

Đếm số cách đặt các quân domino \(1\times2\) hoặc \(2\times1\) lên bảng hình chữ nhật \(m \times n\). Lưu ý, các quân domino không cần phải lấp đầy bảng và không đặt quân domino nào cũng được tính là một cách.

Một ví dụ cho trường hợp \(m = 2, n = 2\):

Input

• Gồm dòng duy nhất chứa 2 số nguyên dương \(m, n\) \((1 \leq m \leq 2, 1 \leq n \leq 10^{12})\).

Output

• Gồm một số nguyên dương là số cách đặt các quân domino sau khi chia lấy dư cho \(998244353\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m = 1, n \leq 20\).
• Subtask \(2\) (\(25\%\) số điểm): \(m = 1, n \leq 10^5\).
• Subtask \(3\) (\(25\%\) số điểm): \(m = 2, n \leq 10\).
• Subtask \(4\) (\(20\%\) số điểm): \(m = 2, n \leq 10^5\).
• Subtask \(5\) (\(10\%\) số điểm): \(m = 2, n \leq 10^{12}\).

Example

1 3

3

2 2

7

Cho dãy số \(n\) nguyên dương \(a_1, a_2, a_3, \dots,a_n\). Gọi \(m(l, r)\) là vị trí của giá trị nhỏ nhất trong đoạn \(a_l, a_{l+1}, \dots, a_r\) (nếu có nhiều số nhỏ nhất thì chọn số có vị trí lớn nhất).
Ta định nghĩa \(f(l, r)\) như sau:

   \(f(l, r) = f(l, m(l, r) - 1) + f(m(l, r) + 1, r) +(r - l + 1)\) nếu \(l \leq r\).
   \(f(l, r) = 0\) nếu \(l > r\).

Có \(q\) truy vấn, mỗi truy vấn gồm hai số nguyên dương \(l, r (1 \leq l \leq r \leq n)\). Với mỗi truy vấn cần tính giá trị \(f(l, r)\).

Input

• Dòng đầu gồm 2 số nguyên dương \(n, q\) \((n, q \leq 10^{6})\).
• Dòng tiếp theo gồm dãy \(a_1, a_2, a_3, \dots, a_n\) \((1 \leq a_i \leq 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương \(l, r\) \((1 \leq l \leq r \leq n)\).

Output

• \(q\) dòng là kết quả của các giá trị \(f(l, r)\) tương ứng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 500\)
• Subtask \(2\) (\(30\%\) số điểm): \(n, q \leq 5000\)
• Subtask \(3\) (\(40\%\) số điểm): \(n, q \leq 10^6\)

Example

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

1
6
8
5
1