Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Artinals
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 243Accepted: 31
Case Time Limit: 2000MS

Description

Nick has recently learned about a special kind of sets called artinian sets or simply artinals. These sets have the advantage of possessing a finite representation, so they can be processed by a computer. However, their formal definition is a bit complicated. Here it is:

  • The only artinal of height ≤ 0 is the empty set ∅.
  • Artinals of heightn are exactly the finite sets composed of artinals of height ≤ n − 1. Here n ≥ 1 is an arbitrary natural number.
  • Finally, A is an artinal if A is an artinal of height ≤ n for at least one integer n.
  • The set of all artinals is denoted by U.
It is immediate from the definition that an artinal of height ≤ n is also an artinal of height ≤ n + 1. Thus for any artinal A we can define its height h(A) as the minimal integer n such that A is an artinal of height ≤ n. An artinal of height n is also called an n-artinal. There were two other definitions which took a lot of time to understand. They are the definition of canonical order on U (denoted by <) and the definition of canonical form of an artinal:
  • The canonical form of an artinal A of height ≤ n is a representation A = {A1, A2, …, As} where Ai are artinals of height ≤ n − 1 and A1 < A2 < … < As.
  • If A = { A1, A2, …, As} and B = { B1, B2 , …, Bt} are two artinals of height ≤ n written in the canonical form, then we put A < B iff there exists an integer k, 1 ≤ k ≤ min(s + 1, t), such that Aj = Bj for all integer j such that 1 ≤ j < k and either k = s + 1 or Ak < Bk.
Now we can define for any artinal A its canonical representation. It is a string repr(A) composed of characters ‘{’, ‘}’ and ‘,’ defined in the following way: repr(∅) = “{}”, and if A is an artinal with canonical form A = {A1, A2, …, As}, then repr(A) = “{” + repr(A1) + “,” + … + “,” + repr(As) + “}”. The canonical representation is often rather lengthy. In order to shorten it, the following definition is introduced. For any integer n ≥ 0 an artinal n (called finite ordinal) is defined by induction on n: 0 := ∅ and n + 1 := {n} ∪ n for all n ≥ 0. Then we can define the reduced canonical representation of an artinal in the following way: We take the canonical representation of this artinal and substitute n for any occurrence of the ordinal n that is not contained in an occurrence of m for some m > n.

Then some operations on artinals are defined. These operations (from highest priority to lowest) are:

  • Unary intersection ∩ : for a non-empty artinal A = {A1, A2, …, As} put ∩A := A1A2 ∩ … ∩ As.
  • Unary union ∪: for any artinal A = {A1, A2, …, As} put ∪A := A1A2 ∪ … ∪ As; ∪∅ := ∅.
  • Binary intersection ∩: AB := {x : xAxB}.
  • Binary union ∪: AB := {x : xA ∨ x ∈ B}.
  • Binary difference −: AB := {xA : xB}.
  • Binary symmetrical difference ⊕: AB := (AB) ∪ (BA).
Besides, some relations between artinals are defined:
  • Equality = and inequality ≠.
  • Inclusion ⊂ and ⊃: (AB) ⇔ (BA) ⇔ (xAxB).
  • Element relations ∈ and ∋: BA (equivalent to AB) means that B is an element of A.
  • Canonical order relations <, >, ≤, ≥ described above (as usual, AB ⇔ ((A < B) ∨ (A = B)), A > BB < A and ABBA).

Now Nick wants you to write a program that would make some computations with artinals. This program will consist of several operators, each on a separate line. There are five kinds of operators:

  • Assignment operator <ident> “:=” <expr> — sets variable <ident> to the value of expression <expr>.
  • Evaluate operator “!”<expr> — evaluates <expr> and prints the result in reduced canonical representation on a separate line of output.
  • Check condition operator “?”<expr><relation><expr> — checks the condition and outputs either “FALSE” or “TRUE” on a separate line of output.
  • Comment operator “#”<any_characters> — the entire line is copied to the output.
  • Empty operator — an empty line (i.e. line consisting only of blank characters) — does nothing.

The following definitions are used:
<ident> ::= <alpha>{<alpha>}
<alpha> ::= <letter>|<digit>|“_”
<digit> ::= “0”|“1”|…|“9”
<letter> ::= “A”|“B”|…|“Z”|“a”|“b”|…|“z”
<expr> ::= “{”[<expr>{“,”<expr>}]“}”|<ident>|<expr><binop><expr>|<unop><expr>|“(”<expr>“)”
<binop> ::= “+”|“*”|“−”|“^”
<unop> ::= “+”|“*”
<relation> ::= “<”|“>”|“=”|“<=”|“>=”|“<>”|“−>”|“<−”|“<<”|“>>”
The binary operators (in the order they were listed in the definition of <binop>) correspond to ∪, ∩, − and ⊕; the unary operators correspond to ∪ and ∩; finally, the relations correspond to <, >, =, ≤, ≥, ≠, ∈, ∋, ⊂, ⊃. Parentheses “(” and “)” are used to change the precedence of operations as usual. All tokens of input (except several <alpha> forming a single <ident>) can be separated by an arbitrary number of blank characters (i.e. spaces and tabulation characters).

Besides, before the execution of the program the variables with names that are decimal representations (without leading zeros) of non-negative integers n ≤ 29 are set to the finite ordinals n. All other variables are initialized with ∅. All identifiers are case-sensitive.

Input

The input file consists of not more than one hundred lines each containing a single operator. No line is longer than 254 characters.

Output

Produce one line of output for each “?”, “!” and “#” operator as described above. It is guaranteed that there will be no “run-time errors” (e.g. unary ∩ will never be applied to an empty set).

Sample Input

  !2    + 2
!2*2
!3-4
 #  More examples!

00 := 5+3
! 3-5
! 00
! (5-3)*(5+3)
? 3>9
A := {2,3,9}
B := {1,7}
! A^ B
! +239
? 2->00
? 2<<00
? A>>B
! {{{},{{}},{}},B,{A},{B},{A,B}}+B

Sample Output

2 
2 
0 
 #  More examples!
0 
5 
{3,4}
FALSE 
{1,2,3,7,9}
238 
TRUE 
TRUE 
FALSE 
{1,2,7,{1,7},{{1,7}},{{1,7},{2,3,9}},{{2,3,9}}}

Source

Northeastern Europe 2003, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator