human
All cinema halls in Berland are rectangles with K rows of K seats each, and K is an odd number. Rows and seats are numbered from 1 to K. For safety reasons people, who come to the box office to buy tickets, are not allowed to choose seats themselves. Formerly the choice was made by a cashier, but now this is the responsibility of a special seating program. It was found out that the large majority of Berland's inhabitants go to the cinema in order to watch a movie, that's why they want to sit as close to the hall center as possible. Moreover, a company of M people, who come to watch a movie, want necessarily to occupy M successive seats in one row. Let's formulate the algorithm, according to which the program chooses seats and sells tickets. As the request for M seats comes, the program should determine the row number x and the segment [yl, yr] of the seats numbers in this row, where yr - yl + 1 = M. From all such possible variants as a final result the program should choose the one with the minimum function value of total seats remoteness from the center. Say,  — the row and the seat numbers of the most "central" seat. Then the function value of seats remoteness from the hall center is . If the amount of minimum function values is more than one, the program should choose the one that is closer to the screen (i.e. the row number x is lower). If the variants are still multiple, it should choose the one with the minimum yl. If you did not get yet, your task is to simulate the work of this program. 

Input

The first line contains two integers N and K (1 ≤ N ≤ 1000, 1 ≤ K ≤ 99) — the amount of requests and the hall size respectively. The second line contains N space-separated integers Mi from the range [1, K] — requests to the program.

Output

Output N lines. In the i-th line output «-1» (without quotes), if it is impossible to find Mi successive seats in one row, otherwise output three numbers x, yl, yr. Separate the numbers with a space.

Examples

Input

2 1
1 1

Output

1 1 1
-1

Input

4 3
1...
Using python3 can you solve the prior task?

Write me a Python code to find Mi successive seats in one row, otherwise output three numbers x, yl, yr?
assistant
#Here is Python code to find Mi successive seats in one row, otherwise output three numbers x, yl, yr.

'''
Jana Goodman6

10B Cinema Cashier

'''
import math
#import time
#import random

SPACE = ' '
MX = 10 ** 16

class Seat:
    def __init__(self, x, y, rem):
        self.x = x
        self.y = y
        self.remoteness = rem
        self.empty = True

class Row:
    def __init__(self, max_seat, x, xc):
        self.max_seat = max_seat
        self.x = x
        self.xc = xc
        self.yc = xc
        self.free_seats = max_seat
        self.seats = [Seat(x, y, self.remoteness(y))
                      for y in range(0, max_seat + 1)]

    def remoteness(self, y):
        return abs(self.x - self.xc) + abs(y - self.yc)

    def total_remoteness(self, y, m):
        return sum(seat.remoteness for seat in self.seats[y:y+m])

    def block_empty(self, y, m):
        return all(seat.empty for seat in self.seats[y:y + m])

    def set_occupied(self, y_left, m):
        for y in range(y_left, y_left + m):
            self.seats[y].empty = False
        self.free_seats -= m

class Cinema:
    def __init__(self, size):
        self.max_seat = size
        self.x_center = math.ceil(self.max_seat / 2)
        self.y_center = self.x_center
        self.seats_left = size * size
        self.rows = [Row(size, x, self.x_center) for x in range(0, size + 1)]

    def get_min_remoteness(self, m):
        if self.seats_left < m:
            return '-1'
        min_remoteness = MX
        min_x, min_yl, min_yr = None, None, None
        for x in range(1, self.max_seat + 1):
            if self.rows[x].free_seats < m:
                continue
            for y in range(1, self.max_seat - m + 2):
                if self.rows[x].block_empty(y, m):
                    rem = self.rows[x].total_remoteness(y, m)
                    if min_remoteness > rem:
                        min_remoteness = rem
                        min_x, min_yl, min_yr = x, y, y + m - 1
        if min_x is None:
            return '-1'
        self.rows[min_x].set_occupied(min_yl, m)
        self.seats_left -= m
        return f'{min_x} {min_yl}...