Diary Box Management

A wooden box is divided into \(n\) rows and \(m\) columns of small cells. The cell in the \(i\)-th row and \(j\)-th column is denoted as \((i,j)\). Wind stores his diaries in this box. Each cell can stack at most \(k\) diaries. Diar ies are always inserted on the top of a cell and can only be removed from the top.

If Wind wants to remove a diary that is not on the top, he must first remove the diaries above it one by one and then re-stack them. For example, if a cell has diaries numbered \(1,2,3,4,5\) from bottom to top, and Wind wants to remove diary \(3\), he must remove diaries \(5\) and \(4\) first. After taking diary \(3\), he places back diaries \(4\) and \(5\) in that order. In this process, he moves \(2\) diaries.

In the following \(t\) days, each day Wind writes a diary with number \(a_i\) and attempts to store it in cell \((x_i, y_i)\). If the cell \((x_i, y_i)\) is already full (i.e. it contains \(k\) diaries), Wind must first remove and destroy the diary with the smallest number. If there are multiple diaries with the smallest number, he destroys the one closest to the top. Note that to remove that diary, he might need to move the diaries above it. After the destruction, he pushes the new diary on the top of the cell.

Your task is to simulate the process over \(t\) days. For each day, output whether a diary was destroyed. If a diary was destroyed, also output the number of diaries that had to be moved in order to remove the smallest diary.

Input Format: The input begins with four integers \(n, m, k, t\). Then \(t\) lines follow, each containing three integers \(a_i, x_i, y_i\), where \(a_i\) is the diary number written on the \(i\)-th day and \((x_i, y_i)\) is the cell where the diary is to be stored. It is guaranteed that the cells are 1-indexed.

inputFormat

The first line of input contains four integers \(n\), \(m\), \(k\), and \(t\) – the number of rows, columns, maximum number of diaries per cell, and the number of days respectively.

Then \(t\) lines follow. The \(i\)-th line contains three integers \(a_i\), \(x_i\), and \(y_i\), representing the diary number written on the \(i\)-th day and the 1-indexed position of the cell where the diary is stored.

outputFormat

Output \(t\) lines. For the \(i\)-th day:

• If the cell \((x_i, y_i)\) is not full, simply store the diary and output NO.
• If the cell is full, remove (destroy) the diary with the smallest number (if there are multiple, remove the one closest to the top). Before removing that diary, Wind must move all the diaries above it. Output YES followed by a space and the number of diaries moved.

sample

1 1 3 4
5 1 1
2 1 1
3 1 1
4 1 1

NO
NO
NO
YES 1