Problem
Petani John terus menjaga kesihatan lembunya, berturut-turut bernombor 1…N.
Baru-baru ini, FD memeriksa mereka semua dan mendapati ada di antara mereka yang sakit. Menggunakan video dari kandang, FD boleh mengetahui pasangan lembu mana yang berinteraksi untuk menyebarkan penyakit itu. FD telah mengumpulkan senarai yang menunjukkan masa interaksi pasangan lembu dalam video (t,x,y) berlaku, bermakna pada masa t lembu x berinteraksi dengan lembu y. FD juga mengetahui perkara berikut:
- Tepat satu lembu pada mulanya dijangkiti (pesakit sifar).
- Setelah seekor lembu dijangkiti, dia menyebarkan jangkitan itu kepada interaksi K seterusnya (mungkin melibatkan pasangan yang sama beberapa kali). Selepas K kali penularan, dia berhenti menularkan jangkitan (apabila menyedari bahawa dia menjangkiti, dia mula mencuci tapak kakinya dengan teliti).
- Sebaik sahaja dia jatuh sakit, dia akan terus sakit.
Malangnya, PD tidak tahu yang mana lembu Nnya adalah "Patient Zero", dan dia tidak tahu nilai K!. Bantu dia mengecilkan julat yang tidak diketahui ini berdasarkan datanya. Jawapannya dijamin wujud.
Input
Baris input pertama mengandungi N (2≤N≤100) dan T (1≤T≤250). Baris seterusnya mengandungi rentetan panjang N, terdiri daripada 0 dan 1, menerangkan keadaan semasa lembu N FD, 0 - sihat, 1 - sakit. Setiap baris T berikut menerangkan kemasukan daripada senarai interaksi FD, dan terdiri daripada tiga nombor, t, x, y, dengan t ialah masa interaksi integer positif (t≤250), x dan y ialah integer berbeza dalam selang 1…N,, menunjukkan lembu mana yang berinteraksi pada masa T. Tidak lebih daripada satu interaksi berlaku pada satu masa T.
Cetakan
Cetak satu baris yang mengandungi tiga integer x, y, z, dengan x ialah bilangan lembu berbeza yang boleh menjadi "pesakit sifar" y - nilai terkecil yang mungkin bagi K yang sesuai dengan data input z - nilai terbesar yang mungkin bagi K yang sesuai dengan data input Jika tiada sempadan atas untuk K, cetak "Infinity"; untuk z. Ambil perhatian bahawa K=0 adalah mungkin.
Contoh
| # |
Input |
Output |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 Infiniti |