Farmer John continues to take care of the health of his cows, consecutively numbered 1…N.
Recently, the FD checked them all and found out that some of them are sick. Using video from the barn, the FD can find out which pairs of cows interacted to spread the disease. The FD has collected a list indicating the time at which the interaction of pairs of cows in the video (t,x,y) took place, meaning that at time t cow x interacted with cow y. The FD also knows the following:
- Exactly one cow was initially infected (patient zero).
- Once a cow is infected, she passes the infection on to her next K interactions (possibly involving the same partner multiple times). After K times of transmission, she stops transmitting the infection (on realizing that she is infecting, she begins to thoroughly wash her hooves).
- Once she gets sick, she stays sick.
Unfortunately, the PD doesn't know which of his N cows is "Patient Zero", and he doesn't know the value of K!. Help him narrow down the ranges of these unknowns based on his data. The answer is guaranteed to exist.
Input
The first input line contains N (2≤N≤100) and T (1≤T≤250). The next line contains a string of length N, consisting of 0 and 1, describing the current state of N FD cows, 0 - healthy, 1 - sick. Each of the following T lines describes an entry from the list of FD interactions, and consists of three numbers, t, x, y, where t is a positive integer interaction time (t≤250), x and y are different integers in the interval 1…N,, indicating which cows interacted at time T. No more than one interaction occurs at one time T.
Imprint
Print one line containing three integers x, y, z, where x is the number of different cows that could be "patient zero" y - the smallest possible value of K that fits the input data z - the largest possible value of K that fits the input data If there is no upper bound for K, print "Infinity"; for z. Note that K=0 is possible.
Examples
| # |
Input |
Output |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 Infinity |