Library Borrowing Requests Management

You are given a library with n books. The i-th book has a fixed number of copies given by an array copies. There are m requests from students to borrow or return these books.

For each request, you will be provided a student ID, a book ID, a request type (either borrow or return), and a timestamp. Requests are given in increasing order of their timestamp.

The process is as follows:

• For a borrow request, if at least one copy of the requested book is available, the student immediately borrows the book and the available copy count decreases by 1. If no copies are available, the request is placed into a pending queue for that book.
• For a return request, the student returns a book they borrowed. The available copy count increases by 1 and if there are any pending borrow requests for that book, the earliest pending request is fulfilled immediately (i.e. the book is issued to that student, and the available copy count decreases by 1 again).

Your task is to simulate the process and output each event (either a successful borrow or a return) in the order they occur.

Mathematically, if we denote the available copies for book i as \(A_i\), then when a borrow request for book i is issued, if \(A_i > 0\), we update \(A_i = A_i - 1\); otherwise, we queue the request. For a return, if the student indeed has the book, \(A_i = A_i + 1\), and if there is a pending request, it is immediately processed.

inputFormat

The first line contains two integers n and m, representing the number of books and the number of requests.

The second line contains n space-separated integers representing the number of copies for each book (from book 1 to book n).

The following m lines each contain a request with four values: a student ID (string), a book ID (integer), a request type (borrow or return), and a timestamp (integer). It is guaranteed that the requests are given in increasing order of timestamp.

outputFormat

For each event (either a successful borrowing or a return), print a line with three items separated by a space: the student ID, the book ID, and the event type (borrowed or returned). The events should be printed in the order they occur.

## sample

3 7
2 1 1
s1 1 borrow 1
s2 1 borrow 2
s3 2 borrow 3
s4 1 borrow 4
s2 1 return 5
s4 1 borrow 6
s3 2 return 7

s1 1 borrowed
s2 1 borrowed
s3 2 borrowed
s2 1 returned
s4 1 borrowed
s3 2 returned

</p>