Cowntact Tracing

Farmer John은 전염성이 매우 강한 소 질병 COWVID-19가 발생한 뒤 소들(늘 그렇듯이 $1 \ldots N$번으로 번호가 매겨져 있다)의 건강을 걱정하고 있다.

최근 Farmer John은 모든 소를 검사했고, 그중 일부가 이 질병에 양성임을 알게 되었다. 헛간 안쪽의 영상 기록을 보면 소들 사이의 최근 접촉을 확인할 수 있다. 소들이 서로 인사할 때 앞발을 흔드는데, 안타깝게도 이 동작으로 한 소에서 다른 소로 감염이 퍼질 수 있다. Farmer John은 서로 접촉한 소 쌍의 목록을 시간 순서와 함께 작성하는데, 각 항목은 $(t, x, y)$ 형태이고 시간 $t$에 소 $x$가 소 $y$와 앞발을 흔들었다는 뜻이다. Farmer John은 다음 사실도 알고 있다.

(i) 농장에서 정확히 한 마리의 소만 처음부터 이 질병을 가지고 있었을 수 있다(이 소를 "patient zero"라고 부르자).

(ii) 소가 감염되면, 그 소는 다음 $K$번의 앞발 흔들기에서 감염을 옮긴다(같은 상대 소와 여러 번 흔드는 경우도 포함될 수 있다). 앞발을 $K$번 흔든 뒤에는 그 뒤의 앞발 흔들기로는 더 이상 감염을 옮기지 않는다(이때쯤이면 자기가 감염을 퍼뜨리고 있다는 것을 깨닫고 앞발을 조심히 씻기 때문이다).

(iii) 소가 감염되면 계속 감염된 상태로 남는다.

안타깝게도 Farmer John은 $N$마리의 소 중 어느 소가 patient zero인지도, $K$의 값도 모른다. 주어진 데이터를 바탕으로 이 미지수들의 가능성을 좁히도록 도와주자. 적어도 하나의 가능성이 유효함이 보장된다.

입력 파일의 첫 줄에는 $N$ ($2 \leq N \leq 100$)과 $T$ ($1 \leq T \leq 250$)가 주어진다. 다음 줄에는 길이 $N$의 문자열이 주어지며, 각 문자는 0 또는 1로 Farmer John의 소 $N$마리의 현재 상태를 나타낸다. 0은 건강한 소를, 1은 현재 질병을 가진 소를 나타낸다. 그다음 $T$개의 줄은 Farmer John의 접촉 목록에 있는 기록을 나타내며, 세 정수 $t$, $x$, $y$로 이루어진다. 여기서 $t$는 접촉이 일어난 양의 정수 시각($t \leq 250$)이고, $x$와 $y$는 $1 \ldots N$ 범위의 서로 다른 정수로 시간 $t$에 어느 소들이 악수를 했는지를 나타낸다. 각 시각에는 최대 한 번의 접촉만 일어난다.

한 줄에 세 정수 $x$, $y$, $z$를 출력한다. $x$는 patient zero가 될 수 있는 소의 수, $y$는 데이터와 일치하는 $K$의 최솟값, $z$는 데이터와 일치하는 $K$의 최댓값이다(데이터에서 추론할 수 있는 $K$의 상한이 없으면 $z$에 "Infinity"를 출력한다). $K=0$인 경우도 가능하다는 점에 유의하자.

patient zero가 될 수 있는 후보는 소 1뿐이다. 모든 $K>0$에 대해 소 1은 시간 7에 소 2를 감염시키고, 소 3과 소 4는 감염되지 않은 상태로 남는다.