코로나 추적

질병관리본부의 본부장은 최근 유행하고 있는 전염병 "COVID-19"의 확산을 걱정하고 있습니다. (모든 사람들은 편의상 $1 \ldots N$ 으로 번호가 매겨져 있습니다).

본부장은 최근 모든 사람들을 검사하여 몇몇 사람들이 질병에 양성 반응을 보인 것을 발견하였습니다. 그는 CCTV 영상을 통해 최근 사람들 간의 상호 작용을 확인할 수 있었습니다.

--- 알고 보니 사람들이 서로 인사할 때 악수를 하는데, 이 행동이 불행하게도 한 사람에서 다른 사람으로 감염을 퍼트릴 수 있었습니다. 본부장은 상호 작용을 한 사람들의 쌍에 대한 시간별 리스트를 작성하였고, 이 리스트에는 $(t, x, y)$ 의 형태로 입력되어 있습니다. 

이것은 시간 $t$에 사람 $x$가 사람 $y$와 악수를 하였다는 것을 의미합니다. 

본부장은 또한 다음 사항들을 알고 있습니다:

(i) 모든 사람들 중 정확히 한 명의 사람만이 처음에 이 질병을 가지고 있을 수 있습니다(우리는 이 사람를 'patient zero'라고 부르겠습니다).

(ii) 사람이 한 번 감염되면, 그는 그의 다음 $K$ 번의 악수를 통해 감염을 전파합니다 (같은 파트너 사람을 여러 번 포함할 수 있습니다).  $K$ 번 악수한 후에는 감염을 더 이상 전파하지 않습니다 (왜냐하면 이 시점에서 그녀는 감염을 퍼트리고 있다는 것을 깨닫고 손을 꼼꼼히 씻기 때문입니다).

(iii) 한 번 사람이 감염되면, 그는 계속 감염 상태를 유지합니다.

불행히도, 본부장은 $N$ 명의 사람 중 누가 'patient zero' 인지, 또는 $K$ 값이 얼마인지 알지 못합니다! 

그의 데이터를 기반으로 이 미지수에 대한 가능성을 좁혀주세요. 적어도 하나의 가능성이 유효하다는 것이 보장됩니다.

입력 파일의 첫 번째 줄에는 $N$ ($2 \leq N \leq 100$)과 $T$ ($1 \leq T \leq 250$)이 주어집니다.

다음 줄에는 길이가 $N$인 문자열이 주어지며, 이 문자열의 항목은 0과 1로 구성되어 있습니다. 

이것은 $N$ 명의 사람들의 현재 상태를 설명합니다. 

0은 건강한 사람을 나타내고, 1은 현재 질병에 걸린 사람을 나타냅니다. 

그 다음 $T$ 줄 각각은 본부장의 상호 작용을 기록한 목록의 기록을 설명하며, 세 개의 정수 $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$에 대해서는 '무한대'를 출력합니다). 

$K=0$이 가능할 수 있음을 유의하세요.