CF200A Cinema

The capital of Berland has the only movie theater in the country. Besides, it consists of only one room. The room is divided into $ n $ rows, each row consists of $ m $ seats. There are $ k $ people lined up to the box office, each person wants to buy exactly one ticket for his own entertainment. Before the box office started selling tickets, each person found the seat that seemed best for him and remembered it as a pair of coordinates $ (x_{i},y_{i}) $ , where $ x_{i} $ is the row number, and $ y_{i} $ is the seat number in this row. It is possible that some people have chosen the same place, then when some people see their favorite seat taken in the plan of empty seats in the theater, they choose and buy a ticket to another place. Each of them has the following logic: let's assume that he originally wanted to buy a ticket to seat $ (x_{1},y_{1}) $ , then when he comes to the box office, he chooses such empty seat $ (x_{2},y_{2}) $ , which satisfies the following conditions: - the value of $ |x_{1}-x_{2}|+|y_{1}-y_{2}| $ is minimum - if the choice is not unique, then among the seats that satisfy the first condition, this person selects the one for which the value of $ x_{2} $ is minimum - if the choice is still not unique, among the seats that satisfy the first and second conditions, this person selects the one for which the value of $ y_{2} $ is minimum Your task is to find the coordinates of a seat for each person.

N/A

N/A