Jenga Boom Simulation

Jane is designing a new version of Jenga Boom. In this game, each block has dimensions \(1 \times w \times w_n\) (thickness \(1\), short side \(w\) and long side \(w_n\)) instead of the ordinary \(1 \times 2 \times 6\). The initial tower is built with \(h\) levels. In each level there are \(n\) blocks placed next to each other along their long sides. Consecutive levels are rotated by \(90^\circ\) relative to each other. Specifically, in odd-numbered levels (1, 3, 5, ...), the blocks are placed horizontally so that each block's footprint is a rectangle with width \(w\) (in the vertical direction) and length \(w_n\) (in the horizontal direction). The centers of the blocks in an odd level are located at \(\big(0,\, (j-\frac{n+1}{2})\,w\big)\) for \(j=1,2,\dots,n\). In even-numbered levels, the blocks are oriented vertically, and their centers are located at \(\big((j-\frac{n+1}{2})\,w,\,0\big)\>.

During the game, players remove blocks one by one according to a given removal sequence. After each removal, the simulator must check the stability of the tower. The tower collapses if there exists a cross-section between two consecutive levels (say between level \(i\) and level \(i+1\)) such that the center of mass \(\big(\bar{x},\bar{y}\big)\) of all blocks above that cross-section does not lie strictly inside the convex hull of the projection of the blocks in level \(i\). Note that if the center of mass lies on the boundary of the convex hull or if level \(i\) has no blocks remaining, the tower is considered to have collapsed.

For a given level, the convex hull is simply the axis–aligned bounding box of the remaining blocks in that level. In an odd (horizontal) level, the bounding box is given by:

[ x_{min}=-\frac{w_n}{2},\quad x_{max}=\frac{w_n}{2},\quad y_{min}=\min\Big{(y_j-\frac{w}{2})\Big},\quad y_{max}=\max\Big{(y_j+\frac{w}{2})\Big} ]

where \(y_j=(j-\frac{n+1}{2})\,w\) for each remaining block \(j\). Similarly, for an even (vertical) level, the bounding box is:

[ y_{min}=-\frac{w_n}{2},\quad y_{max}=\frac{w_n}{2},\quad x_{min}=\min\Big{(x_j-\frac{w}{2})\Big},\quad x_{max}=\max\Big{(x_j+\frac{w}{2})\Big} ]

The center of mass for the blocks in levels above (say levels \(i+1\) to \(h\)) is computed as the average of the centers of all remaining blocks in those levels. For an odd level the block center is \((0, (j-\frac{n+1}{2})w)\) and for an even level it is \(((j-\frac{n+1}{2})w, 0)\).

Your task is to simulate the removals in the given order. The input provides the tower parameters and the removals. After each removal, check all cross-sections (from level 1 to level \(h-1\)). Report the index (1-indexed) of the removal that causes the tower to collapse, or output stable if the tower remains standing after all removals.

inputFormat

The first line contains five integers: \(h\) \(n\) \(w\) \(w_n\) \(m\) where \(h\) is the number of levels, \(n\) is the number of blocks per level, \(w\) is the short side length, \(w_n\) is the long side length, and \(m\) is the number of removals.

Each of the next \(m\) lines contains two integers \(l\) and \(r\) indicating that the block in level \(l\) (1-indexed from the bottom) and position \(r\) (1-indexed within the level) is removed. It is guaranteed that a block is removed at most once.

outputFormat

If the tower collapses, output the 1-indexed move number at which collapse occurs. Otherwise, output stable.

sample

3 3 2 6 3
1 1
3 3
1 3

stable