Film

Time limit2sMemory limit512 MB

Summary
Given experiments that combine two films with AND or OR over red, green, blue bits, decide whether some color assignment to all films makes every experiment consistent.
Level

Medium7 of 10

Topics
Union-find, Bit manipulation, Math, Implementation
Solved
No attempts yet

Problem

While excavating a ruin, the archaeologist Lyut found a record that appears to be a trace of aliens living on the alien planet rdd-6584. Comparing it with other records, Lyut learned that this record is the result of experiments on a special film. According to the record, this film comes in several colors, and is made up only of the three primary colors. Therefore a film's color can be expressed by the presence or absence of the three monochromatic lights red, green, and blue, giving 8 possible colors in total.

\

Lyut found m experiment records from experiments on n of these films. The films are numbered from 1 to n. One experiment consists of stacking two films and shining light of a particular wavelength on them to observe which color appears. The light shone is made up of a sum of one or more monochromatic lights. Unusually, the color observed through this film depends on the wavelength. If light of a wavelength higher than the reference is shone, then for each monochromatic light contained in that light, the film reflects that monochromatic light only if both films have it. Conversely, if light of a wavelength lower than the reference is shone, then for each monochromatic light contained in that light, the film reflects that monochromatic light only if at least one of the two films has it. The observed color is the union of all reflected monochromatic lights.

Lyut wants to determine whether this experiment record is truly a record of alien experiments or merely scribbles. Lyut decides to call an experiment record an alien experiment record if it satisfies the following condition.

  • Every experiment must be free of error. That is, there is at least one way to assign colors to all films so that the light reflected according to wavelength matches what is described above.

Given an experiment record, Lyut wants to judge whether this record is an alien's or merely scribbles. Help Lyut.

Input

The first line gives the number of films n (1 ≤ n ≤ 50,000) and the number of experiment records m (1 ≤ m ≤ 200,000), separated by a space.

From the second line to the m+1-th line, each experiment record is given in the form A B K C1 C2.

A is the number of the first film and B is the number of the second film. (1 ≤ A, B ≤ n) K is the height of the wavelength: H if higher than the reference, L if lower. C1 and C2 are the colors of the shone light and the observed light, respectively. C1 and C2 are each one of the color names given in the table. Note that C1 is never BLACK under the conditions.

Output

If it is an alien experiment record, print “ALIEN”; otherwise, print “THINKINGFACE”.

Examples2

  1. Example 1

    Input
    3 5
1 3 L WHITE YELLOW
1 3 H CYAN GREEN
1 2 L WHITE WHITE
2 3 H RED BLACK
2 1 L PURPLE PURPLE
    Expected output
    ALIEN

  2. Example 2

    Input
    3 4
1 3 L WHITE YELLOW
2 3 H GREEN BLACK
1 3 H PURPLE BLUE
1 2 L CYAN CYAN
    Expected output
    THINKINGFACE