Under construction

Still being built. Things may change

Equality Control

Time limit2sMemory limit512 MB

Summary
Given two BALLOON programs built from list literals, concat, shuffle, and sorted, decide whether they return every list with the same probability.
Level

Medium7 of 10

Topics
String, Recursion, Implementation
Solved
No attempts yet

Problem

In programming contest circles, one of the most important roles is that of the Chief Equality Officer (CEO). This person makes sure that every team has an equal chance of winning the contest. After last year's NWERC, the current CEO, Gregor, spent a long time thinking about how to make the contest even fairer.

His answer is to make a new programming language the only one allowed for submissions. No team is disadvantaged by not having mastered one of the allowed languages. The language is called BALLOON, short for Building A Long List Of Ordinary Numbers. Its only data type is the list of integers. To keep the language fast, it has only four instructions:

  • [x1,...,xn] is the constructor for lists. It returns the integers inside the brackets in their given order.
  • concat(<Expr1>,<Expr2>) returns the integers from evaluating <Expr1>, followed by the integers from evaluating <Expr2>.
  • shuffle(<Expr>) returns the integers from <Expr> rearranged by a uniformly random permutation. Each permutation is used with equal probability.
  • sorted(<Expr>) returns the integers from <Expr> rearranged in non-decreasing order.

For example, take concat(shuffle([1,2]),shuffle([1,2])). Each shuffle takes [1,2] and returns either [1,2] or [2,1], each with probability 0.50.5, independently of the other. The outer concat joins the two results. So it returns [1,2,1,2], [1,2,2,1], [2,1,1,2], or [2,1,2,1], each with probability 0.250.25.

Output is probabilistic, so submissions cannot be checked by comparing bytes. The judge instead checks whether a submitted program is equivalent to the judges' sample solution. Two programs are equivalent if, for every list LL of integers, both programs return LL with the same probability.

Your task is to determine whether two given BALLOON programs are equivalent.

Input

The input consists of:

  • One line containing a string A, the first program.
  • One line containing a string B, the second program.

Each program has between 3 and 10610^6 characters. Programs contain no spaces and no empty lists, so the strings (a space) and [] never occur in the input. Each integer in a program is greater than 0 and less than 10910^9.

Output

Print equal if the two programs are equivalent, and not equal otherwise.

Examples3

  1. Example 1

    Input
    concat(shuffle([1,2]),shuffle([1,2]))
    shuffle([1,2,1,2])
    
    Expected output
    not equal
    
  2. Example 2

    Input
    sorted(concat([3,2,1],[4,5,6]))
    [1,2,3,4,5,6]
    
    Expected output
    equal
    
  3. Example 3

    Input
    concat(sorted([4,3,2,1]),shuffle([1]))
    concat(concat([1,2,3],shuffle([4])),sorted([1]))
    
    Expected output
    equal