Một trí tuệ nhân tạo cần kết nối với một máy chủ từ xa để đồng bộ hóa dữ liệu. Máy chủ này hoạt động theo một chu kỳ cố định để bảo trì và tối ưu hiệu năng:

• \(X\) giây ở trạng thái Online (cho phép kết nối);
• Sau đó, \(S\) giây ở trạng thái Offline (từ chối mọi kết nối).

Chu kỳ này lặp lại liên tục và bắt đầu từ giây thứ 1 với trạng thái Online.

Yêu cầu: Một trí tuệ nhân tạo gửi yêu cầu kết nối đến máy chủ vào giây thứ \(T\). Hãy kiểm tra tại giây thứ \(T\), máy chủ đang ở trạng thái Online hay Offline?

Input

• Dòng đầu tiên gồm số nguyên dương \(X\) \((1 \leq X \leq 10^9)\).
• Dòng thứ hai gồm số nguyên dương \(S\) \((1 \leq S \leq 10^9)\).
• Dòng thứ ba gồm số nguyên dương \(T\) \((1 \leq T \leq 10^9)\).

Output

• Nếu tại giây thứ \(T\) máy chủ đang Offline ghi ra số 0, máy chủ đang Online ghi ra số 1.

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(T \leq 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): không có ràng buộc thêm.

Example

5
7
5

1

5
7
20

0

Nhân dịp Tết Trung thu, khu phố đã treo \(N\) chiếc đèn lồng có màu vàng và màu đỏ, từ trái sang phải. Một dãy đèn lồng liên tiếp được gọi là “đẹp” nếu số lượng đèn màu vàng gấp đôi số lượng đèn màu đỏ.

Yêu cầu: Cho một xâu \(S\) chỉ gồm các ký tự V và D mô tả dãy đèn lồng, ký tự V mô tả đèn lồng màu vàng và ký tự D mô tả đèn lồng màu đỏ. Hãy tìm độ dài của dãy đèn lồng “đẹp” dài nhất.

Input

• Một xâu \(S\) chỉ gồm các ký tự V và D mô tả dãy đèn có độ dài không vượt quá \(10^5\).

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): độ dài xâu \(S\) không vượt quá \(100\).
• Subtask \(2\) (\(20\%\) số điểm): độ dài xâu \(S\) không vượt quá \(1000\).
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc thêm.

Example

VDVVDDVVD 

6

Trong một khu rừng có \(N\) cây. Các cây được đánh số từ \(1\) đến \(N\), có tất cả \(M\) loại cây.

Cây thứ \(i\) thuộc loại \(B_{i}\) \((1 \leq B_{i} \leq M)\) và có chiều cao là \(C_{i}\).

Chênh lệch chiều cao của rừng cây được tính theo công thức: tổng các giá trị tuyệt đối của hiệu chiều cao giữa tất cả các cặp cây khác loại nhau. Nghĩa là chênh lệch chiều cao của rừng cây được tính bằng công thức:

Yêu cầu: Hãy tính chênh lệch chiều cao của rừng cây đã cho.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) \((1 \leq N \leq 10^5; M \leq N)\);
• Dòng thứ hai gồm \(N\) số nguyên dương \(B_{i}\) \((1 \leq B_{i} \leq M)\);
• Dòng thứ ba gồm \(N\) số nguyên dương \(C_{i}\) \((1 \leq C_{i} \leq 10^9)\).

Output

• Một số nguyên duy nhất là chênh lệch chiều cao của rừng cây đã cho.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \leq N \leq 1000; 1 \leq C_{i} \leq 200\);
• Subtask \(2\) (\(20\%\) số điểm): \(1 \leq N \leq 10^5; M = 2\);
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc thêm.

Example

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

14

Với hai số nguyên dương \(X, Y\) cho trước, dãy F-Fibonacci là dãy số được định nghĩa như sau:

• \(F_{0} = 𝑋; F_{1} = Y\).
• \(F_{i} = F_{i−1} + F_{i−2}\) với mọi \(i \geq 2\).

Cho dãy \(A\) gồm \(N\) số nguyên dương \(A_{1}, A_{2}, A_{3}, \ldots, A_{N}\). Người ta muốn chia dãy \(A\) thành các đoạn con liên tiếp sao cho tổng các phần tử của mỗi đoạn con đều thuộc dãy F-Fibonacci.

Yêu cầu: Hãy đếm số cách chia dãy \(A\) thành các đoạn con sao cho tổng các phần tử của mỗi đoạn
con đều thuộc dãy F-Fibonacci.

Input

• Dòng đầu tiên gồm số nguyên dương \(N\) \((1 \leq N \leq 10^5)\);
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1}, A_{2}, A_{3}, \ldots, A_{N}\) \((1 \leq A_{i} \leq 10^9; 1 \leq i \leq N)\);
• Dòng thứ ba gồm hai số nguyên dương \(X\) và \(Y\) \((1 \leq X \leq Y \leq 100)\).

Output

• Một số nguyên duy nhất là kết quả bài toán sau khi chia dư cho \(10^{9} + 7\).

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \leq N \leq 20; 1 \leq A_{i} \leq 10^{5} (1 \leq i \leq N)\);
• Subtask \(2\) (\(40\%\) số điểm): \(1 \leq N \leq 1000\).
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc thêm.

Example

6
1 3 2 2 1 4
1 1

4

Trong sứ mệnh khám phá bản đồ số, một rô-bốt tự hành được giao một nhiệm vụ di chuyển dọc theo một dãy gồm \(N\) điểm thu thập thông tin, được đánh số từ \(1\) đến \(N\).

Điểm thu thập thông tin \(i\) \((1 \leq i \leq N)\) có lượng dữ liệu là \(A_{i}\), nếu rô-bốt thu thập thông tin tại điểm này thì sẽ tiêu thụ \(W_{i}\) năng lượng.

Rô-bốt được lập trình để quét các điểm thông tin liên tiếp và phải tuân thủ nghiêm ngặt các điều kiện sau:

• Số lượng điểm thu thập thông tin được quét phải là bội số của \(K\) (để đảm bảo tính toàn
  vẹn của các gói thông tin);
• Tổng năng lượng tiêu thụ để rô-bốt thu thập thông tin không được vượt quá giới hạn \(S\) của pin. Coi năng lượng tiêu thụ khi di chuyển qua các điểm thông tin bằng \(0\).

Yêu cầu: Hãy viết chương trình lập trình cho rô-bốt để tìm ra các điểm thông tin liên tiếp thỏa mãn điều kiện trên mà tổng lượng dữ liệu thu thập được là lớn nhất.

Input

• Dòng đầu tiên gồm ba số nguyên \(N, K\) và \(S\) \((1 \leq K \leq N \leq 10^5; 1 \leq S \leq 10^{12})\);
• Dòng thứ hai gồm \(N\) số nguyên \(A_{1}, A_{2}, \ldots, A_{N}\) \((|A_{i}| \leq 10^{9}; 1 \leq i \leq N)\);
• Dòng thứ ba gồm \(N\) số nguyên \(W_{1}, W_{2}, \ldots, W_{N}\) \((0 \leq W_{i} \leq 10^{9}; 1 \leq i \leq N)\).

Output

• Gồm một số nguyên là lượng dữ liệu thu thập được lớn nhất. Nếu không tồn tại các điểm thông tin liên tiếp nào khả thi, ghi ra số \(0\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \leq 100\);
• Subtask \(2\) (\(25\%\) số điểm): \(W_{i} = 0\) \((1 \leq i \leq N)\);
• Subtask \(3\) (\(25\%\) số điểm): \(K = 1\);
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc thêm.

Example

5 2 6
3 -1 2 5 -2
2 1 2 2 1

7

3 2 5
10 20 5
1 1 1

30