Hard Refactoring

Interview

Time limit2sMemory limit512 MB

Summary

Merge a union of integer intervals given as comparisons, then reprint the merged ranges using the fewest possible constants, with special handling for saturated ends and all-true or all-false cases.

Level: Medium6 of 10
Topics: Intervals, Sorting, Implementation, Math
Solved: No attempts yet

Problem

Helen found a piece of code that uses a lot of "magic constants". One of the things she found is a logical expression that checks whether an integer x belongs to a union of ranges, like this one:

x >= 5 && x <= 10 ||
x >= 7 && x <= 20 ||
x <= 2 ||
x >= 21 && x <= 25 ||
x >= 8 && x <= 10 ||
x >= 100

Helen dislikes magic constants, so she decided to refactor this expression and every similar one. The refactored expression must give the same Boolean result as the original for every integer x, and it must contain as few integer constants in its text as possible.

Every integer in this problem, including x, lies in the signed 16 bit range: at least $-2^{15} = -32768$ and at most $2^{15} - 1 = 32767$ .

Input

The input has between 1 and 1000 lines. Each line is either one comparison, or two comparisons joined by the logical and operator &&. A comparison starts with x, then the greater-or-equals operator >= or the less-or-equals operator <=, then an integer constant. When a line holds two comparisons, the first one uses >= and the second one uses <=.

Every line except the last ends with the logical or operator ||. Tokens on a line are separated by a single space, and no line has leading or trailing spaces.

Output

Print the refactored expression in the same format as the input. It must give the same Boolean result as the original expression for every integer x, and it must contain the smallest possible number of integer constants.

Several texts can reach that minimum, so the required output form is fixed:

Split the set of integers x that satisfy the original expression into maximal ranges that do not touch each other.
Print one line per maximal range, in increasing order of the left endpoint.
A range $[-32768, b]$ whose lower end is $-32768$ is written x <= b.
A range $[a, 32767]$ whose upper end is $32767$ is written x >= a.
Any other range $[a, b]$ is written x >= a && x <= b.
Every line except the last ends with ||.

Write constants without leading zeros, and put exactly one space between tokens on a line.

If the expression is true for every integer x, print a single line with the word true. If it is false for every integer x, print a single line with the word false.

Examples4

Example 1

Input

x >= 5 && x <= 10 ||
x >= 7 && x <= 20 ||
x <= 2 ||
x >= 21 && x <= 25 ||
x >= 8 && x <= 10 ||
x >= 100

Expected output

x <= 2 ||
x >= 5 && x <= 25 ||
x >= 100

Example 2
Input
```
x >= 10 && x <= 0
```
Expected output
```
false
```
Example 3
Input
```
x <= 10 ||
x >= 0
```
Expected output
```
true
```
Example 4
Input
```
x >= -32768
```
Expected output
```
true
```