Room Booking System

This problem simulates a room booking system. There are n rooms, each available for 366 days (days are numbered from 1 to 366). The system supports four operations:

• BO r d₁ d₂: Book room r for all days from d₁ to d₂ (inclusive). However, if any day in this range is already booked, the booking is ignored.
• CN r d₁ d₂: Cancel the booking of room r from day d₁ to day d₂. If there is no booking for some of these days, nothing happens for those days.
• CH r d: Check if room r is available on day d. Output "Available" if it is free, or "Booked" otherwise.
• LB d₁ d₂: List all bookings between days d₁ and d₂ (inclusive). Each booking is represented as a pair (room number, day). The listings should be in ascending order of room number and day.

You are given an initial line with two integers: n (the number of rooms) and q (the number of queries). Then exactly q queries follow. The system processes the queries in order and outputs results immediately for the check and list bookings operations.

Note: All formulas are represented in LaTeX when applicable; for instance, the booking range is given by \(d_1\) and \(d_2\) where \(1 \leq d_1 \leq d_2 \leq 366\).

inputFormat

The input is read from standard input (stdin). The first line contains two integers n and q representing the number of rooms and the number of queries, respectively. The following q lines each contain one query. The queries are in one of the following four formats:

• BO r d1 d2
• CN r d1 d2
• CH r d
• LB d1 d2

Each query token is separated by spaces.

outputFormat

Output to standard output (stdout). For a CH (check) query, print a single line with either "Available" or "Booked". For an LB (list bookings) query, print one line per booking, where each line contains the room number and the day, separated by a space. The outputs for different queries should be printed in the order of their appearance in the input.

## sample

3 5
BO 1 10 12
BO 2 11 13
CH 1 11
CN 1 11 11
CH 1 11

Booked
Available

</p>