ml2 | Plagiarism Detection

Giorgio is pursuing a career as a singer-songwriter! However, the music world is tough, and you always need to watch out for plagiarism. In fact, the last song that Alessandro wrote sounds suspiciously similar to one of Giorgio’s songs, and now Giorgio wants to prove Alessandro’s mischief.

Both Giorgio’s and Alessandro’s songs are $N$ notes long. Each note is encoded by two integers between $0$ and $V$: its duration $d_i$, followed by its pitch $p_i$. Each song is then encoded as a sequence of $2 \cdot N$ integers.

Of course, the plagiarism case will be uncontroversial if the two songs are identical. If not, the plagiarism case will be stronger if Giorgio can find a short contiguous sequence of notes that needs to be modified to transform Giorgio’s song into Alessandro’s.

For such a sequence, if possible, it would be better for Giorgio if he can prove that applying some of these classical tune transformations transforms his song into Alessandro’s:

• Transposition: increase or decrease every pitch in the sequence by the same amount;
• Doubling (resp. halving): double (resp, halve) every duration in the sequence;
• Retrogradation: invert the sequence of notes, playing them from the last one to the first.

Note that each operation can be used at most once.

Help Giorgio file his claim on Alessandro’s mischief as strongly as possible by finding the shortest sequence to change!

Input data

The first line contains the two integers $N$ and $V$.

The next $N$ lines contain two integers each ($d_i$ and $p_i$) describing Giorgio’s song.

The next $N$ lines contain two integers each ($d_i$ and $p_i$) describing Alessandro’s song.

Output data

You need to write a single line with one of the following contents:

• SAME: if the two songs are identical;
• TRANSFORMED L: if Alessandro’s song can be obtained by modifying a sequence of length $L$ using some of the operations described above;
• ORIGINAL L: there is a sequence of length $L$ that cannot be obtained just by applying the operations described above

Constraints and clarifications

• $1 \leq N \leq 100 \ 000$;
• $1 \leq V \leq 10^9$;
• $0 \leq d_i, p_i \leq V$;

Example 1

stdin

3 127
48 60
48 62
96 64
48 60
48 62
96 64

stdout

SAME

Explanation

In the first sample case, the two songs are identical.

Example 2

stdin

6 127
48 60
48 62
48 64
96 60
48 62
96 64
48 60
48 62
96 64
48 60
48 62
96 64

stdout

ORIGINAL 2

Explanation

In the second sample case, Alessandro’s song is obtained by rewriting the third and fourth notes $48 \ 64$, $96 \ 60$ into $96 \ 64$, $48 \ 60$, leaving the rest unchanged. Note that this is not obtainable through a combination of some classical tune transformations.

Example 3

stdin

7 127
48 60
48 62
48 64
96 60
48 62
48 64
96 60
48 60
24 67
48 65
24 69
24 67
48 64
96 60

stdout

TRANSFORMED 4

Explanation

In the third sample case, Alessandro’s song can be obtained by transforming the sequence from the second note to the fifth, by applying halving, retrogradation and then a $+5$ transposition.