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ộ 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 \le X \le 10^9~);
• Dòng thứ hai gồm số nguyên dương ~S~ (~1 \le S \le 10^9~);
• Dòng thứ ba gồm số nguyên dương ~T~ (~1 \le T \le 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.

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.

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 \le B_i \le 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: ~\sum |C_i - C_j| \forall 1 \le i < j \le N \text{ và } B_i \neq B_j~.

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 \le N \le 10^5~; ~M \le N~);
• Dòng thứ hai gồm ~N~ số nguyên dương ~B_i~ (~1 \le B_i \le M~);
• Dòng thứ ba gồm ~N~ số nguyên dương ~C_i~ (~1 \le C_i \le 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.

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 = X; F_1 = Y~;
• ~F_i = F_{i-1} + F_{i-2}~ với mọi ~i \ge 2~.

Cho dãy ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, \dots, 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 \le N \le 10^5~);
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ (~1 \le A_i \le 10^9~; ~1 \le i \le N~);
• Dòng thứ ba gồm hai số nguyên dương ~X, Y~ (~1 \le X \le Y \le 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~.

Trong sứ mệnh khám phá bản đồ, 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 \le i \le 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 để thu thập 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 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, S~ (~1 \le K \le N \le 10^5~; ~1 \le S \le 10^{12}~);
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~|A_i| \le 10^9~; ~1 \le i \le N~);
• Dòng thứ ba gồm ~N~ số nguyên ~W_1, W_2, \dots, W_N~ (~0 \le W_i \le 10^9~; ~1 \le i \le 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 khả thi, ghi ra số 0.