Rectangular Island Channel Grid

An urban legend tells that Peter the Great once considered transforming an island into a masterpiece of engineering by digging channels that turn entire rows or columns into water. The island is modeled as a rectangular grid of size \(h\) (height) and \(w\) (width). Initially, every cell is dry land. When a channel is dug through a complete row or column, all cells in that row or column become water. The resulting dry land cells (those that were never turned into water) may then form several connected components. Two dry cells are connected if they share a side (i.e. they are adjacent vertically or horizontally).

Your task is to plan the channel digging such that the grid ends up with exactly \(n\) connected components of dry land.

How does channel digging partition the grid?

If you carefully choose to dig channels only on internal rows and columns (i.e. not on the boundary), the dry cells will form contiguous blocks. More precisely, if you dig \(x\) rows (with \(x \ge 0\)) and \(y\) columns (with \(y \ge 0\)) in such a way that none of the dug rows is the first or last row and none of the dug columns is the first or last column, the dry cells will split into \( (x+1) \) segments vertically and \( (y+1) \) segments horizontally. Therefore, the number of connected components of dry land is exactly \[ (x+1)\times(y+1). \]

Your goal is to choose appropriate \(x\) and \(y\) (and then specify which rows and columns to dig) such that \((x+1)\times (y+1)= n\), while also ensuring that there is enough room in the grid to place these channels. In particular, to get \(x+1\) dry segments from the rows, you must pick \(x\) channels from the set \(\{2, 3, \dots, h-1\}\) ensuring that there is at least one dry row between consecutive channels (i.e. they are not consecutive numbers). This is possible if and only if \[ 2\times (x+1)-1 \le h, \quad \text{or}\quad x+1 \le \frac{h+1}{2}. \] Similarly, for the columns, you need \(y+1 \le \frac{w+1}{2}\).

If a valid plan exists, output the plan as described below. Otherwise, output -1.

inputFormat

The input consists of a single line containing three space-separated integers: \(h\) \(w\) \(n\) — the number of rows, the number of columns, and the desired number of connected components of dry land respectively.

Constraints:

• \(1 \le h, w \le 10^9\) (practically, the grid will be large enough to consider channels only when planning properly)
• \(1 \le n \le 10^9\)

outputFormat

If a valid plan exists, output two lines:

• The first line begins with an integer \(k\) — the number of rows to dig as channels, followed by \(k\) distinct integers in increasing order representing the indices of the rows (1-indexed). These rows must not be the first or last row (i.e. not 1 or \(h\)) and must be chosen such that there is at least one dry row between any two dug channels.
• The second line begins with an integer \(l\) — the number of columns to dig as channels, followed by \(l\) distinct integers in increasing order representing the indices of the columns (1-indexed). These columns must not be the first or last column and must be chosen so that there is at least one dry column between any two dug channels.

If there is no valid plan that results in exactly \(n\) connected components, output a single line containing -1.

Note: If \(n=1\), output \(0\) on each line (since no channels are required).

sample

3 3 4

1 2
1 2