AZUL — Placement order on the wall (v4)
=======================================

This is an OUTPUT-ONLY task. There are 10 test cases. For each test you submit
the contents of an output file (a placement order of the cells in the input);
nothing is compiled or executed against your submission. The checker reads
your output file, validates it as a permutation of the occupied cells of the
input board, computes the resulting Azul wall-placement score, and converts
that score to a per-test credit using the formula at the bottom.

The problem
-----------
You are given a final occupied configuration on an m x n grid: a subset of
cells marked 'X' (occupied) and the rest marked '.' (empty). You must output
an ordering of the occupied cells. The ordering is scored using the standard
Azul wall-placement scoring (ignoring row/column/colour bonuses and
penalties):

When placing cell x while a set P of cells has already been placed, define:

  h(x, P) = 1 + the number of consecutive already-placed cells immediately to
            the left and right of x in the same row.
  v(x, P) = 1 + the number of consecutive already-placed cells immediately
            above and below x in the same column.

The score contributed by placing x is:

  1                                      if h(x,P) == 1 and v(x,P) == 1
  (h(x,P) if h>1, 0 otherwise) +
  (v(x,P) if v>1, 0 otherwise)           otherwise

The total score is the sum of contributions across all N placements. Your
goal is to maximise this total.


Input format
------------
The first line of each input contains four integers:

    m  n  s  t

where m and n are the grid dimensions (rows, columns), s is the BASELINE
score on this test, and t is the TARGET score (the best score known across
reference solvers). s and t are informational; your program does not need to
read them, but they are provided so you can compute a local estimate of your
credit.

Each of the next m lines is a string of exactly n characters from {'X', '.'}
describing one row of the grid.


Output format
-------------
Output N lines (where N is the number of 'X' cells in the grid), each
containing the 1-indexed row and column of the next cell to place:

    r_1 c_1
    r_2 c_2
    ...
    r_N c_N

Any invalid output (wrong count, duplicates, missing cells, off-board cells)
scores 0 on that test.


How the tests are generated
---------------------------
Every test is produced by a single procedure with four parameters:

  seed         (int)             RNG seed
  n            (int)             the board has an n x n grid of blocks
  block_size   (int)             each block is block_size x block_size cells
  density      (p_lo, p_hi)      bounds of an iid per-block density

The board is partitioned into an n-by-n array of (block_size x block_size)
blocks, separated by a single empty cell between adjacent blocks. Inside each
block, an independent density p is drawn from Uniform[p_lo, p_hi], every cell
is then marked X with probability p (independently across cells), and we
keep only the largest 4-connected component of that block. All other cells
(within the block and outside any block) remain '.'.

The board side is exactly  n * (block_size + 1) - 1.

Pseudocode (the actual generator is shipped alongside as generator.py):

  function generate(seed, n, block_size, density):
      lo, hi  = density
      rng     = Random(seed)
      stride  = block_size + 1
      cells   = empty set
      for br in 0 .. n-1:
          for bc in 0 .. n-1:
              p = rng.uniform(lo, hi)
              block = empty set
              for dr in 0 .. block_size-1:
                  for dc in 0 .. block_size-1:
                      if rng.random() < p:
                          add (dr, dc) to block
              block = largest_4-connected_component(block)
              for (dr, dc) in block:
                  add (br * stride + dr, bc * stride + dc) to cells
      return cells


Per-test parameters
-------------------
The 10 tests cover a sweep from "everything filled" through "many tiny
blobs" to "a few huge blobs", with two density variants (medium / very
dense) at the medium and large scales, and one sparse below-percolation
test at large scale:

  #   name           seed   n     s     density        board   #blocks  comments
  01  full_table     100    1    480   (1.00, 1.00)     480       1     one solid 480x480
  02  tiny_blobs     200    96    4    (0.55, 0.70)     479    9216    each component <= 16 cells (exact-DP solvable)
  03  small_blobs    300    48    8    (0.55, 0.66)     431    2304    small random-blob components
  04  medium_blobs   500    22   20    (0.55, 0.66)     461     484    medium random-blob components
  05  medium_dense   600    22   20    (0.85, 0.99)     461     484    nearly-solid medium squares
  06  large_sparse   400    8    58    (0.40, 0.50)     471      64    below-percolation tree-like fragments
  07  large_blobs    700    8    58    (0.55, 0.66)     471      64    large random-blob components
  08  large_dense    800    8    58    (0.85, 0.99)     471      64    nearly-solid large squares
  09  huge_blobs     900    3   159    (0.55, 0.66)     479       9    9 huge random-blob components
  10  gigantic      1000    2   239    (0.55, 0.66)     479       4    4 enormous random-blob components

Note: in 01 the density of (1, 1) means every cell of the single 480x480 block
is occupied; in 02 the parameter block_size=4 keeps each blob below the cap
of the exact-DP solver shipped as a reference. Tests 06 (sparse) and 08
(dense) at large scale (n=8, s=58) bracket the "ordinary" random-blob test 07
on either side of the percolation threshold (~0.593).


Scoring (per test)
------------------
Let S be the score your placement order achieves on the test. Then

    frac   = clamp((S - s) / (t - s), 0, 1)
    credit = 0                          if S <  s   (strictly below baseline)
           = 0.1 + 0.9 * frac^10        if S >= s

The 0.1 floor is awarded the moment you reach the baseline s, and 0.9 is
split toward the target t with a steep exponent (frac=0.9 banks 0.9^10 ~=
0.35 of the remaining 0.9). The test's contribution to your total is

    points = 10 * credit

(every test has weight 10). A submission that ties the baseline on every
test scores exactly 10 points; one that hits every target scores 100.
