GOODD - Good Code

no tags 

It's time for the members of The Team to do what they do best - coding! Faster than you can say "Dijkstra", they've already produced an elegant piece of work. The program has $N$ ($1 \leq N \leq 10^6$) lines of code (conveniently numbered $1..N$), and just one integer variable, $c$, which starts with a value of 0. The program starts executing at line 1, and every line $i$ contains one of the following:

  1. "c++;" - The value of $c$ is incremented by 1. Then, if $i=N$, the program terminates - otherwise, the program moves to line $i+1$.
  2. "x:" - This line contains the label $x$, where $x$ is an integer such that $1 \leq x \leq 10^6$. No value of $x$ will appear as a label more than once in the program. If $i=N$, the program terminates - otherwise, the program moves to line $i+1$.
  3. "goto x;" - The program jumps to the single line that contains the label $x$, where $x$ is an integer such that $1 \leq x \leq 10^6$. It is guaranteed that, for every such line, the corresponding label will exist in the program.

Now, even though this program is glorious, its creators are wondering if it's quite correct. In particular, they know that $c$ should ideally reach a value of $M$ ($1 \leq M \leq 10^{12}$), but they're not sure when. If the program terminates with $c

Input

First line: 2 integers, $N$ and $M$

Next $N$ lines: The $i$th line of the program (as described above), for $i=1..N$

Output

Either 1 integer, the number of the line on which $c$ will first reach a value of $M$, or the string "WA" if the program terminates with $c

Example

Input:
12 4
c++;
goto 6;
18:
c++;
c++;
goto 2;
goto 6;
6:
goto 18;
2:
c++;
c++;

Output:
11

Explanation of Sample

The program will run through the following lines, and corresponding values of $c$:

  • Line 1 ("c++;"), $c=1$
  • Line 2 ("goto 6;"), $c=1$
  • Line 8 ("6:"), $c=1$
  • Line 9 ("goto 18;"), $c=1$
  • Line 3 ("18:"), $c=1$
  • Line 4 ("c++;"), $c=2$
  • Line 5 ("c++;"), $c=3$
  • Line 6 ("goto 2;"), $c=3$
  • Line 10 ("2:"), $c=3$
  • Line 11 ("c++;"), $c=4$

As can be seen, $c$ first achieves a value of $M=4$ on line 11.


hide comments
nadstratosfer: 2018-04-12 08:17:09

Long thinking how to represent the problem correctly, short coding, solution immediately producing intended result; I go through this pattern in about every problem by SourSpinach. Had fun as always, thanks.

Adesh Atole: 2015-04-04 20:48:23

Error at 6th Test Case (TLE)


Added by:SourSpinach
Date:2013-05-09
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64