There is a metric graph $G = (V, E)$ that satisfies the following properties:

• $G$ is a weighted complete undirected graph.
• For any three distinct points $x, y, z \in V$, the edge weights satisfy the triangle inequality, i.e., $d(x, z) \leq d(x, y) + d(y, z)$.

Given a value $k$, we want to partition the nodes into $m$ sets $S_1, S_2, \dots, S_m$ such that:

• $\forall i \neq j, S_i \cap S_j = \emptyset$
• $S_1 \cup S_2 \cup \dots \cup S_m = V$
• $\forall i, |S_i| \geq k$, meaning each set must contain at least $k$ nodes.

For each set $S_i$, choose a center node $c_i \in S_i$. Define the radius $r_i$ of $S_i$ as the maximum distance from any point in $S_i$ to $c_i$, i.e., $r_i = \max_{x \in S_i} d(x, c_i)$.

The goal is to minimize the maximum of $r_i$. Output any valid partition that minimizes this maximum radius. (Note: Different subtasks have different scoring methods.)

Input

The first line contains three integers $n, k, sub$, representing the number of nodes in $G$, the lower bound on the size of each set, and the subtask number.

The next $n$ lines each contain $n$ integers, where the $j$-th integer in the $i$-th line represents the edge weight $d(i, j)$ between nodes $i$ and $j$.

Output

The first line contains an integer $m$, representing the number of sets.

The next $m$ lines each contain the size $|S_i|$ followed by $|S_i|$ integers representing the node indices in $S_i$.

The last line contains $m$ integers, where the $i$-th integer is $c_i$, the center node chosen for $S_i$.

Constraints

For all data, $n \leq 200, 0 \leq d(i, j) \leq 10^6$.

• Subtask 1 (20 pts): $n \leq 15$
• Subtask 2 (20 pts): The graph $G$ is generated as follows:
  1. Generate $n$ integers $a_1, a_2, \dots, a_n$.
  2. Let $V = \{1, 2, \dots, n\}$, and let the edge weight between $i$ and $j$ be $|a_i - a_j|$.
• Subtask 3 (20 pts): $k > \frac{n}{3}$
• Subtask 4 (40 pts): Let $R$ be the radius of the solution output by the contestant, and let $R^*$ be the optimal radius. The score for the contestant is $S \cdot e^{\min\{0, 2 - \frac{R}{R^*}\}}$, where $S$ is the score for the data point. The subtask score is the minimum of all data point scores. Note that a full score is obtained if $\frac{R}{R^*} \leq 2$.

Examples

Input 1

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

Output 1

3
1 1
1 2
1 3
1 2 3

Input 2

4 2 2
0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0

Output 2

2
2 1 2
2 3 4
1 3