Static Analysis for X Language

X Language is a simple programming language with only two integer variables, x and y. The variable x is provided as input (any value in the C++ int range) and y is initialized to 0. An X Language program consists of several lines, each containing exactly one command of one of the following three types:

• if (condition) {
• y = number;
• } (which ends a conditional block)

The condition in an if-statement is either x > number or x < number, where number is a constant between 1 and 10⁹. The semantics of the if-statement and assignment are the same as in C++: if the condition is true, the block is executed, otherwise it is skipped. Note that there is no else branch. A program may contain nested if-statements. Your task is to write a static analyzer which, given an X Language program, computes all possible values of y at the end of the program (over all feasible inputs x that satisfy the conditions along the execution path).

Hint: You may simulate program execution by performing a depth-first search over the possible branches. On encountering a condition x > c, the branch where the condition holds corresponds to adding the constraint x > c (or x ≥ c+1), and the branch where it fails corresponds to x ≤ c. Similar reasoning applies for conditions of the form x < c (with the condition holding corresponding to x < c i.e. x ≤ c-1 and failing corresponding to x ≥ c).

inputFormat

The input begins with an integer n indicating the number of lines in the X Language program. The following n lines each contain one command of the program. It is guaranteed that the syntax of the program is valid.

Note: The value of x is not provided in the input, as it comes from the external environment and could be any integer in the C++ int range.

outputFormat

Output all possible final values of y (after the program execution) in increasing order, separated by a single space.

sample

3
if (x > 10) {
y = 5;
}

0 5