Herding the Goats

In a magical war, the battlefield known as Golden Village is modeled as a 3D grid (a rectangular cuboid) with unit cells whose coordinates range from \( (0,0,0) \) to \( (n-1, m-1, k-1) \). Initially, \( t \) battleships of distinct levels suddenly appear at \( t \) different cells. From each battleship, an army of goats is spawned. At each unit of time, the goats from every occupied cell spread to the 6 adjacent cells (up, down, left, right, forward, backward). If an adjacent cell is already occupied, no goats are spread into that cell. If two (or more) groups of goats simultaneously try to occupy the same cell, the group originating from the battleship with the higher level wins the cell.

After a while, every cell in Golden Village will be occupied by goats. Your mission, as the newly appointed officer, is to determine the territorial extent (i.e. the number of cells claimed) of each battleship’s goat army. The battleships are given in the input in a fixed order. In case of ties (i.e. when multiple battleships can reach a cell at the same time), the goats from the battleship with the higher level will conquer that cell.

Note: The propagation of goats follows the rule that the time to reach a cell is equal to the Manhattan distance from the cell to the battleship's initial position. Thus, a cell \( (x,y,z) \) will be reached by a battleship located at \( (x_0, y_0, z_0) \) in \( |x-x_0|+|y-y_0|+|z-z_0| \) time units. In case two or more battleships yield the same time, the one with the higher level prevails.

inputFormat

The input begins with a line containing three integers \( n, m, k \) representing the dimensions of the grid.

The next line contains an integer \( t \) indicating the number of battleships.

Then \( t \) lines follow. Each of these lines contains four integers: \( x\ y\ z \ L \), where \( (x,y,z) \) is the coordinate (0-indexed) of a battleship and \( L \) is its level. The \( t \) battleships are given in a fixed order and occupy distinct cells. It is guaranteed that all levels are distinct.

outputFormat

Output a single line containing \( t \) integers. The \( i^{th} \) integer denotes the total number of cells ultimately occupied by the goat army originating from the \( i^{th} \) battleship (in the input order).

sample

2 2 2
2
0 0 0 5
1 1 1 3

4 4