Book Borrowing Management

You are given a set of books, students, and borrowing requests. Each book is identified by an ID and has a limited number of copies available. Each student is identified by an ID and has a priority level. For each borrowing request, process it as follows:

• If either the book ID or student ID does not exist, output invalid request.
• If the book is available (i.e. there is at least one copy remaining), decrement the available copies and output borrowed.
• If the book is not available, output waitlisted.

Process the requests in the order they are provided.

Note: All formulas, if any, should be written in LaTeX format. In this problem, there are no formulas to display.

inputFormat

The input is read from standard input (stdin) and has the following format:

<b> <s> <r>
<book_id1> <copies1>
...
<book_id_b> <copies_b>
<student_id1> <priority1>
...
<student_id_s> <priority_s>
<timestamp1> <student_id_request1> <book_id_request1>
...
<timestamp_r> <student_id_request_r> <book_id_request_r>

Here, the first line contains three integers: the number of books b, the number of students s, and the number of requests r. The following b lines each contain the book ID and the number of copies available for that book. The next s lines each contain a student ID and the student's priority level. The final r lines each contain three integers: a timestamp, a student ID, and a book ID corresponding to a borrowing request.

outputFormat

The output should be printed to standard output (stdout). For each borrowing request, output a single line indicating the status of the request. The status can be one of the following:

• borrowed - if the book is available and the borrowing is successful.
• waitlisted - if the book is not available at the time of the request.
• invalid request - if the book ID or student ID is not valid.

## sample

2 3 5
1 2
2 1
1 10
2 5
3 20
1 2 1
2 1 2
3 1 2
4 3 1
5 2 1

borrowed
borrowed
waitlisted
borrowed
waitlisted

</p>