Playlists#518

Playlists

... Possibly some cool legend might appear here any time soon ...

You have playlists. Each playlist is a list of songs. Each song has its rating. In other words, playlist s_i is a list of songs \left[ s_{i,1}, s_{i,2}, \dots, s_{i,k_i} \right], where k_i is the length of the list.

You want to listen to playlists in some order. Assume you are listening to playlists in the order of s_1, s_2, \dots, s_n. Then the songs will be a list \left[ s_{1,1}, s_{1,2}, \dots, s_{1, k_1}, s_{2, 1}, s_{2,2}, \dots, s_{n, k_n} \right].

Let us say a list of songs \left[ a_1, a_2, \dots, a_k \right] is "great" if and only if a_i > \sum_{j < i} a_j for all 1 \le i \le k, i.e., each song has a bigger rating than all previous songs combined.

Please find the longest "great" prefix among all orderings of playlists.

Input

The first line contains a single integer (1 \le n \le 10^3) — the number of playlists.

The following lines define the playlists.

The -th line contains a single integer k_i (1 \le k_i \le 10^6) — the number of songs in the playlist .

The (2i + 1)-th line contains k_i integers s_{i, 1}, s_{i, 2}, \dots, s_{i, k_i} (0 \le s_{i, j} \le 10^9, s_{i,j} = 2^t for some ) — the ratings of the songs in the playlist.

It is guaranteed that \sum_{i=1}^{n} k_i \le 10^6.

Output

In the first line, print a single integer — the length of the longest "great" prefix.

In the second line, print integers — the order of playlists that achieves such a result.

If there are several possible orders, print any.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first example, with the order (1, 2, 3) the songs are [1, 4, 8, 32]:

  • 1 > 0,,

  • 4 > 1,,

  • 8 > 1 + 4 = 5,,

  • 32 > 1 + 4 + 8 = 13,.

All four songs satisfy the condition, so the great prefix has length . No other ordering of the three playlists achieves a longer great prefix.

In the second example, with the order (2, 1, 4, 3) the songs are [1, 2, 4, 8, 128, 256, 2]:

  • 1 > 0,

  • 2 > 1,

  • 4 > 1 + 2 = 3,

  • 8 > 1 + 2 + 4 = 7,

  • 128 > 1 + 2 + 4 + 8 = 15,

  • 256 > 1 + 2 + 4 + 8 + 128 = 143,

  • 2 \not> 1 + 2 + 4 + 8 + 128 + 256 = 399.

The great prefix has length .

Scoring

  1. ( points) n \le 3;

  2. ( points) n \le 8;

  3. ( points) k_i = 1;

  4. ( points) s_{i,j} < 32;

  5. ( points) no additional restrictions.