Inside the large kingdom, there is an infinite dining hall. It can be represented as a set of cells ((x, y)), where (x) and (y) are non-negative integers. There are an infinite number of tables in the hall. Each table occupies four cells ((3x + 1, 3y + 1)), ((3x + 1, 3y + 2)), ((3x + 2, 3y + 1)), ((3x + 2, 3y + 2)), where (x) and (y) are arbitrary non-negative integers. All cells that do not belong to any of the tables are corridors. There are (n) guests that come to the dining hall one by one. Each guest appears in the cell ((0, 0)) and wants to reach a table cell. In one step, they can move to any neighboring by side corridor cell, and in their last step, they must move to a neighboring by side a free table cell. They occupy the chosen table cell, and no other guest can move there. Each guest has a characteristic (t_i), which can either be (0) or (1). They enter the hall in order, starting to walk from the cell ((0, 0)). If (t_i=1), the (i)-th guest walks to the nearest vacant table cell. If (t_i=0), they walk to the nearest table cell that belongs to a completely unoccupied table. Note that other guests may choose the same table later. The distance is defined as the smallest number of steps needed to reach the table cell. If there are multiple table cells at the same distance, the guests choose the cell with the smallest (x), and if there are still ties, they choose among those the cell with the smallest (y). For each guest, find the table cell which they choose. The first line contains a single integer (q) ((1 \leq q \leq 5000)) — the number of test cases. Then follows their description. The first line of each test case contains a single integer (n) ((1 \leq n \leq 50\,000)) — the number of guests. The second line of each test case contains (n) integers (t_1, t_2, \ldots, t_n) ((t_i \in \{0, 1\})) — the characteristics of the guests. It is guaran