Hyperspace Jump (어려운 버전)

지금은 125년이 지난 뒤이지만, 인류는 여전히 자신들을 파괴하려는 인간형 사이보그 종족에게서 도망치고 있다. 아니면 여기서 몇몇 이야기가 뒤섞인 것일지도 모른다... 어쨌든 함대는 이제 더 작아졌다. 그러나 최근의 개량으로 모든 항법 시스템에 고차원 선형대수 도약 처리 장치가 장착되었다.

이제 도약하려면 함장이 사건이 일어나는 d차원 공간의 부분 공간을 지정해야 한다. 함장은 그 부분 공간을 생성하는 벡터 집합을 제공하여 이를 지정한다.

Princess Heidi는 m척의 각 함선의 함장에게서 그러한 집합을 받았다. 그녀는 다시 한번 초공간 도약 부분 공간이 같은 함선들을 묶고 싶다. 이를 위해 각 함선에 1부터 m 사이의 그룹 번호를 할당하여, 두 함선에 대응하는 부분 공간이 같을 때, 그리고 그럴 때에만 두 함선이 같은 그룹 번호를 갖게 하려고 한다(서로 다른 벡터 집합을 사용해 주어졌을 수도 있다).

Help Heidi!

입력의 첫째 줄에는 공백으로 구분된 두 정수 m와 d (2 ≤ m ≤ 30 000, 1 ≤ d ≤ 5)가 주어진다. 각각 함선의 수와 전체 기저 벡터 공간의 차원이다. 다음으로 m개의 부분 공간이 차례로 설명된다. i-th번째 함선에 대응하는 i-th번째 부분 공간은 다음과 같이 설명된다.

첫째 줄에는 정수 하나 ki (1 ≤ ki ≤ d)가 주어진다. 이어서 ki개의 줄이 주어지며, 그중 j-th번째 줄은 i-th번째 함선이 보낸 j-th번째 벡터를 설명한다. j개의 각 줄은 벡터 를 설명하는, 공백으로 구분된 d개의 정수 aj, j = 1, ..., d로 이루어지며, |aj| ≤ 250이 성립한다. i-th번째 부분 공간은 이 ki개 벡터의 선형 생성 공간이다.

공백으로 구분된 m개의 정수 g1, ..., gm을 출력한다. 여기서 는 i-th번째 함선에 할당된 그룹 번호를 나타낸다. 즉, 임의의 1 ≤ i < j ≤ m에 대해 다음이 성립해야 한다. i-th번째 부분 공간과 j-th번째 부분 공간이 같을 때, 그리고 그럴 때에만 gi = gj이다. 또한 수열 (g1, g2, ..., gm)은 이 성질을 만족하는 모든 수열 중 사전순으로 가장 작아야 한다.

예제 테스트 케이스에서 첫 번째 부분 공간과 마지막 부분 공간은 같고, 부분 공간 2부터 4까지는 서로 같으며, 부분 공간 5부터 7까지도 서로 같다.

벡터 의 생성 공간으로 주어진 한 부분 공간과 벡터 의 생성 공간으로 주어진 다른 부분 공간은, 각 벡터 vi를 벡터 w1, ..., wk (that is, there exist coefficients such that vi = α1w1 + ... + αkwk)의 선형 결합으로 나타낼 수 있고, 마찬가지로 각 벡터 wi를 벡터 v1, ..., vn의 선형 결합으로 나타낼 수 있을 때 서로 같다는 것을 기억하라.

어떤 인덱스 i, 1 ≤ i ≤ m가 존재하여 gi < hi이고 모든 j < i에 대해 gj = hj이면, 수열 (g1, g2, ..., gm)은 수열 (h1, h2, ..., hm)보다 사전순으로 작다는 것을 기억하라.