... 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.
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.
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.
Example 1
Example 2
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 .
( points) n \le 3;
( points) n \le 8;
( points) k_i = 1;
( points) s_{i,j} < 32;
( points) no additional restrictions.