Có hai robot đang chuyển động thẳng đều, cùng chiều trên cùng một con đường, robot thứ nhất đang ở vị trí ~S_1~ đang di chuyển với vận tốc là ~V_1 \ m/s~, robot thứ hai đang ở vị trí ~S_2~ di chuyển với vận tốc là ~V_2 \ m/s~. Hỏi sau bao nhiêu lâu thì hai robot gặp nhau?

Dữ liệu nhập vào từ file văn bản DRB.INP:

• Dòng đầu tiên gồm số nguyên dương ~S_1~ mô tả vị trí của robot thứ nhất~;~
• Dòng thứ hai gồm số nguyên dương ~V_1~ mô tả vận tốc của robot thứ nhất~;~
• Dòng thứ ba gồm số nguyên dương ~S_2~ mô tả vị trí của robot thứ hai~;~
• Dòng thứ tư gồm số nguyên dương ~V_2~ mô tả vận tốc của robot thứ hai.

Các đơn vị khoảng các được tính bằng mét, thời gian được tính bằng giây và ~S_1≠S_2 \ ;~ ~S_1,S_2,V_1,V_2≤10^9~.

Kết quả ghi ra file văn bản DRB.OUT:

In ra một số nguyên là phần nguyên của kết quả - thời gian mà hai robot gặp nhau. Nếu hai robot không thể gặp nhau thì in ra ~-1~.

Ví dụ

Input

2
5
7
3

Output

2

Giải thích: Sau ~2.5~ giây hai robot sẽ gặp nhau:

• ~2+5 \times 2.5=14.5 ~.
• ~7+3 \times 2.5=14.5~ .

Phần nguyên của ~2.5~ là ~2~.

Input

2
3
7
5

Output

-1

Giải thích: Hai robot càng đi càng xa nhau.

Trong phòng thí nghiệm, các nhà khoa học đang nghiên cứu về gen của một chuỗi ARN đặc biệt được mã hóa bằng một xâu ~S~ gồm các kí tự ~'A', \ 'U', \ 'G', \ 'X'~. Họ muốn cắt từ chuỗi ARN đó một mạch (được mã hóa bằng xâu ~X~ cho trước).

Yêu cầu: Từ chuỗi ARN ~S~ có thể cắt được ra tối đa bao nhiêu đoạn mạch ~X~.

Dữ liệu nhập vào từ file văn bản ARN.INP:

• Dòng đầu tiên gồm một xâu kí tự ~S~ mô tả chuỗi ARN~;~
• Dòng thứ hai gồm một xâu kí tự ~X~ mô tả đoạn mạch cần cắt ra.

Các xâu chỉ gồm các kí tự ~'A', \ 'U', \ 'G', \ 'X'~ và độ dài các xâu không quá ~10^3~ kí tự.

Kết quả ghi ra file văn bản ARN.OUT:

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

Ví dụ

Input

AUAUGXXAUGXGX
AUGX

Output

2

Giải thích: AUAUGXXAUGXGX

Input

AAAAA
AAA

Output

1

Giải thích: AAAAA

Input

AGAX
U

Output

0

Do ảnh hưởng của dịch bệnh, các lớp học sẽ học kết hợp cả hình thức trực tiếp và trực tuyến. Để học sinh có thể hiểu kĩ hơn về bài học, giáo viên lưu lại video các bài giảng và tải lên nhóm lớp cho học sinh xem lại.

Một video bài giảng dài ~Z~ giây. Dung lượng mà video cần phát ~1~ giây là ~X~ MB. Nhưng mạng nhà An lúc đó chỉ có thể tải được ~Y~ MB trong ~1~ giây. An muốn xem bài giảng mà không phải dừng lại giữa chừng. An quyết định trước khi bắt đầu xem, sẽ đợi được ~T_0~ giây để bài giảng được tải xuống một dung lượng nhất định. Một video bài giảng được phát liên tục nếu tổng dung lượng tại thời điểm bất kì mà An đã tải về lớn hơn hoặc bằng tổng dung lượng của đoạn video tính đến thời điểm đó.

Yêu cầu: Hãy giúp An tìm xem lượng thời gian ít nhất ~T_0~ mà An phải đợi để có thể xem liên tục.

Dữ liệu nhập vào từ file văn bản TBG.INP:

Gồm một dòng gồm ba số nguyên dương ~X,Y,Z~ ~(1≤X,Y,Z≤10^5; \ Y \lt X)~.

Kết quả ghi ra file văn bản TBG.OUT:

Một số nguyên ~T_0~ là thời gian ít nhất mà An phải đợi.

Ràng buộc

• Có ~80\%~ số test ứng với ~80\%~ số điểm của bài thoả mãn: ~1≤X,Y,Z≤100;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

4 1 1

Output

3

Giải thích:

• An đợi trước ~3~ giây nên An đã tải được sẵn ~3 \times 1=3~ MB.
• Tại giây thứ nhất của video, dung lượng mà An tải được sẽ là ~3+1=4~ MB, vừa bằng dung lượng mà video phát trong ~1~ giây là ~4~ MB.

Input

10 3 2

Output

5

Giải thích:

• An đợi trước ~5~ giây nên An đã tải được sẵn ~5 \times 3=15~ MB.
• Tại giây thứ nhất của video, dung lượng mà An tải được sẽ là ~15+3=18~ MB. Lớn hơn dung lượng mà video phát trong ~1~ giây là ~10~ MB.
• Tại giây thứ ~2~ của video, dung lượng mà An tải được sẽ là ~18+3=21~ MB. Lớn hơn dung lượng mà video phát trong ~2~ giây là ~20~ MB.

Cho một hình chữ nhật gồm ~N~ dòng và ~M~ cột. Các dòng được đánh số từ ~1~ đến ~N~, từ trên xuống dưới. Các cột được đánh số từ ~1~ đến ~M~, từ trái sang phải. Ô ở dòng thứ ~i~ và cột thứ ~j~ được gọi là ô ~(i,j)~ và có diện tích là ~1~ đơn vị. Có một số ô đã được điền sẵn kí tự ~'X'~.

Yêu cầu: Tìm hình chữ nhật con có diện tích lớn nhất chỉ chứa duy nhất một kí tự ~'X'~.

Dữ liệu nhập vào từ file văn bản HCN.INP:

• Dòng đầu tiên gồm ba số nguyên dương ~N,M,K~ ~(N,M≤10^4; \ K≤10^3)~ mô tả kích thước của hình chữ nhật và số lượng kí tự ~'X'~ có trong hình chữ nhật~;~
• ~K~ dòng sau, mỗi dòng gồm hai số nguyên dương ~d~ và ~c~ là chỉ số dòng và cột của ô điền kí tự ~'X'~ ~(d≤N; \ c≤M)~.

Kết quả ghi ra file văn bản HCN.OUT:

Ghi ra diện tích của hình chữ nhật lớn nhất thoả mãn yêu cầu đề bài.

Ràng buộc

• Có ~50\%~ số test tương ứng với ~50\%~ số điểm thoả mãn: ~N,M≤50;~
• ~30\%~ số test khác tương ứng với ~30\%~ số điểm thoả mãn: ~N,M≤500;~
• ~20\%~ số test còn lại tương ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

4 5 4
2 3
2 5
3 1
4 4

Output

9

Giải thích:

Bình mua bán cổ phiếu VNI trên thị trường chứng khoán. Giả sử giá của một cổ phiếu VNI trong vòng ~N~ ngày lần lượt là ~A_1,A_2,…,A_N~. Biết rằng mỗi ngày Bình chỉ thực hiện một trong những hoạt động sau:

1. Mua một cổ phiếu VNI~;~
2. Bán số lượng cổ phiếu VNI bất kì mà Bình đang sở hữu~;~
3. Không thực hiện bất kì giao dịch nào.

Yêu cầu: Bình thực hiện mua bán cổ phiếu VNI như thế nào để thu được lợi nhuận lớn nhất nếu anh ấy tham gia mua bán bắt đầu từ ngày thứ ~T~ cho trước?

Dữ liệu nhập vào từ file văn bản VNI.INP:

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(N≤10^5)~ là số ngày biết giá cổ phiếu~;~
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_1,A_2,…,A_N~ tương ứng là giá của một cổ phiếu VNI trong từng ngày ~(A_i≤10^9; 1≤i≤N);~
• Dòng thứ ba gồm một số nguyên dương ~Q~ là số lượng truy vấn ~(Q≤10^5);~
• ~Q~ dòng sau, mỗi dòng gồm một số nguyên dương ~T~ ~(T≤N)~ thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu VNI.

Kết quả ghi ra file văn bản VNI.OUT:

~Q~ dòng, mỗi dòng gồm một số nguyên duy nhất là lợi nhuận lớn nhất mà Bình thu được ở mỗi truy vấn tương ứng.

Ràng buộc

• Có ~50\%~ số test tương ứng với ~50\%~ số điểm thoả mãn: ~N≤1000; \ Q=1;~
• ~30\%~ số test khác tương ứng với ~30\%~ số điểm thoả mãn ~N≤10^5; \ Q=1;~
• ~20\%~ số test còn lại tương ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

4
1 2 5 4
2
1
3

Output

7
0

Giải thích:

• Bình bắt đầu tham gia mua bán VNI vào ngày ~1~:
  • Ngày ~1~: mua ~1~ VNI với giá là ~1~.
  • Ngày ~2~: mua ~1~ VNI với giá là ~2~.
  • Ngày ~3~: bán ~2~ VNI với giá là ~5~.
  • Ngày ~4~: không mua hay bán VNI vào ngày này.

~\Rightarrow~ Lợi nhuận thu được là: ~-1-2+2 \times 5=7~.

• Bình bắt đầu tham gia mua bán VNI vào ngày ~3~:
  • Bình không mua bán VNI vào ngày ~3~ và ngày ~4~.

~\Rightarrow~ Lợi nhuận thu được là: ~0~.