Girls Invitational '19 S3 - GOTO

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

You are given a piece of code consisting of N lines from your friend! Unfortunately, your friend only knows the GOTO, PRINT, and QUIT statements, and has created a jumbled mess that you must now debug!

The description of each statement is as follows:

  • GOTO i Jump to line i. If this statement is on line j, it is guaranteed 1 \le i \le N, i \ne j. The lines are 1-indexed.
  • PRINT k Output the integer k (1 \le k \le 5) to the screen, followed by a newline. Then, continue to the next line in the program. It is guaranteed that such a line exists (and is not the end of the program).
  • QUIT Exit the program.

In addition to being given the program, you have also been given the expected output. Since the program is such a jumbled mess, you want to salvage some sections of it. In particular, you want to know from which lines the program can begin at such that the expected output is created, and the program exits.

Input Specification

The first line will contain the integer N (1 \le N \le 10^4), the number of lines of code.

The next N lines will each contain a statement as described above.

The next line will contain the integer M (0 \le M < N), the number of lines in the expected output.

The next M lines will each contain one integer p (1 \le p \le 5), an integer in the expected output.

Output Specification

On the first line, print Q space-separated integers, in sorted order, the lines that the program could begin at to create the expected output. Q is the number of such lines that the program could begin at. If Q = 0, print nothing.

Subtasks

Subtask 1 [70%]

For the first operation, i > j. In other words, GOTO will always jump to a line further down than line j.

Subtask 2 [30%]

No further constraints.

Sample Input 1

7
QUIT
GOTO 4
GOTO 5
PRINT 3
GOTO 6
PRINT 4
QUIT
1
4

Sample Output 1

3 5 6

Sample Input 2

8
GOTO 5
QUIT
QUIT
QUIT
GOTO 1
PRINT 1
QUIT
GOTO 1
0

Sample Output 2

2 3 4 7

Notes

For Python users, it is recommended to submit in Python, not PyPy, for this problem.


Comments

There are no comments at the moment.