Có $n$ bộ bài trên bàn, bộ thứ $i$ gồm $a_i$ lá và lá thứ $j$ từ trên xuống là $s_{i,j}$. Để đơn giản hóa bài toán, ta chỉ xét bài cao và bài thấp. Nếu lá bài là bài cao thì $s_{i,j}=1$. Nếu là bài thấp thì $s_{i,j}=0$.

Có $m$ người chơi ngồi quanh bàn chờ chơi bài. Bạn là người chia bài và nhiệm vụ của bạn là xếp tất cả các bộ bài thành một chồng lớn. Bạn chỉ có thể điều khiển thứ tự giữa các bộ bài. Bạn không được thêm hay bỏ lá bài, cũng không được thay đổi thứ tự các lá trong một bộ.

Sau khi xếp xong chồng bài, bài sẽ được chia cho người chơi. Người chơi thứ $i$ sẽ nhận các lá thứ $i$, $m+i$, $2m+i$, $\ldots$, $km+i$, $\ldots$ từ trên xuống. Những người chơi khác không biết rằng người chơi thứ $b$ thực ra là sếp của bạn. Để đảm bảo chiến thắng, tất cả các lá chia cho sếp phải là bài cao và tất cả các lá chia cho những người chơi khác phải là bài thấp.

Hãy tìm thứ tự xếp các bộ bài thỏa mãn yêu cầu này hoặc thông báo rằng không thể thực hiện. Nếu tồn tại đáp án hợp lệ, hãy đưa ra đáp án nhỏ nhất theo thứ tự từ điển.

Đáp án, nếu tồn tại, hiển nhiên là một hoán vị có độ dài $n$. Ta nói hoán vị $P=p_1,p_2,\ldots,p_n$ nhỏ hơn hoán vị $Q=q_1,q_2,\ldots,q_n$ theo thứ tự từ điển nếu tồn tại số nguyên $t$ sao cho $p_i=q_i$ với mọi $1\le i<t$ và $p_t<q_t$.

Dữ liệu vào

Mỗi tệp kiểm thử chỉ có một bộ dữ liệu.

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n$, $m$ và $b$ ($1\le n\le2\times10^5$, $2\le m\le2\times10^5$, $1\le b\le m$), lần lượt là số bộ bài, số người chơi và chỉ số của sếp.

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa xâu $s_{i,1}s_{i,2}\cdots s_{i,a_i}$ ($s_{i,j}\in\{0,1\}$, $1\le a_i\le10^6$), mô tả bộ bài thứ $i$.

Đảm bảo rằng:

• Mỗi bộ bài có ít nhất một lá bài cao.

• Tổng số lá bài chia hết cho $m$.

• Tổng số lá bài không vượt quá $10^6$.

Dữ liệu ra

Nếu tồn tại đáp án hợp lệ, in $n$ số nguyên $d_1,d_2,\ldots,d_n$ cách nhau bởi dấu cách, biểu diễn đáp án nhỏ nhất theo thứ tự từ điển, trong đó $d_i$ là chỉ số của bộ bài thứ $i$ trong chồng bài từ trên xuống.

Nếu không tồn tại đáp án hợp lệ, chỉ in “-1” (không có dấu ngoặc kép).

Ví dụ

Dữ liệu vào 1

5 4 3
0100010
00100
001000100
0010
0100010

Dữ liệu ra 1

2 1 3 5 4

Dữ liệu vào 2

4 2 1
010
10101
010
10101

Dữ liệu ra 2

2 1 4 3

Dữ liệu vào 3

1 5 3
001000010000100

Dữ liệu ra 3

1

Dữ liệu vào 4

2 5 3
01000
00010

Dữ liệu ra 4

-1

Dữ liệu vào 5

1 5 3
11111

Dữ liệu ra 5

-1