EXCHANGE - Đổi tiền
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: AresGod

Vì là một học sinh ngoan nên TSL sắp được thầy 333 cho đi du lịch qua Singapore và Korea (để thăm Tú oppa). Thật may mắn, nhà của TSL đã có sẵn 2 loại tiền của 2 nước này với giá trị lần lượt là N và M. Nhưng theo tính toán, TSL cần phải mang theo đúng X giá trị tiền Singapore và Y giá trị tiền Korea để có thể tận hưởng niềm vui trọn vẹn (và vì bản tính ăn chơi tiêu xài vô độ nên TSL không muốn sau khi có X tiền Singapore và Y tiền Korea thì còn dư bất kỳ đồng nào nữa). Máy đổi tiền trước nhà của TSL có 2 loại chức năng:

-     L x y mang ý nghĩa đổi đúng x tiền Singapore sang đúng y tiền Korea

-     R x y mang ý nghĩa đổi đúng y tiền Korea sang đúng x tiền Singapore

Vì muốn tiết kiệm thời gian để đi chơi với gái, à không, để chuẩn bị đồ đạc cần thiết cũng như nghỉ ngơi, TSL muốn biết được số bước ít nhất sau một số lần quy đổi để có thể đạt được đúng X tiền Singapore và Y tiền Korea cũng như số cách đổi ít nhất như vậy (để đề phòng cách này có vấn đề thì vẫn còn cách khác), ngoài ra thì thời gian của TSL chỉ còn lại t đơn vị. Vì vậy, nếu sau t đơn vị thời gian mà không có cách đổi ra thì in ra 2 số -1. Biết rằng một lần máy đổi tiền hoạt động sẽ tốn 1 đơn vị thời gian và thời điểm ban đầu TSL đi đổi tiền là thời điểm 0.

Input:

-   Dòng đầu là 3 số nguyên N, M và t (1 ≤ N,M ≤ 100, 1 ≤ t ≤500) là số tiền Singapore và Korea mà TSL hiện đang có và thời gian t.

-   Dòng 2 là số nguyên K (1 ≤ K ≤ 5) là số chức năng của máy đổi tiền.

-   K dòng tiếp theo mỗi dòng sẽ có dạng: L (hoặc R) và 2 số nguyên x và y (1 ≤ x,y ≤ 10)

-   Dòng tiếp theo là số nguyên Q (1 ≤ Q ≤ 106 ) là số truy vấn.

-   Q dòng tiếp theo mỗi dòng gồm 2 số nguyên X và Y là số tiền Singapore và Korea mà TSL muốn có (1 ≤ X,Y ≤ 1000).

Ouput:

Gồm Q dòng trả lời cho từng truy vấn trong input:

 -    Nếu truy vấn này sau thời gian t vẫn chưa có được cách đổi thì in ra 2 số -1.

 -    Nếu có cách đổi thì in ra 2 số lần lượt là số bước ít nhất để có được tiền thỏa mãn của từng truy vấn và số cách đổi như vậy. Vì kết quả số cách đổi có thể rất lớn nên in ra phần dư khi chia số cách đổi cho 106 + 3.

Ví dụ

  • input
    1 1 5
    3
    L 1 2
    R 1 1
    L 2 3
    2
    1 2
    2 1
    output
    2 2
    3 2
Back to Top