Unchanged Picture

Time limit5sMemory limit128 MB

Summary
Determine whether two plotter-drawn vector pictures are geometrically similar under translation, rotation, and uniform scaling but no mirroring.
Level

Hard8 of 10

Topics
Geometry, String matching, Math
Solved
No attempts yet

Problem

Steganography is a special way to protect messages: instead of encrypting a message, it is hidden somewhere. One digital steganographic technique is to hide a small piece of information inside a digital image. The modification of the image is so small that a human eye cannot notice it, yet a computer can read the hidden information (such as a text message). In this problem, your task is to compare two images and find such (possibly very small) differences.

Here we focus on vector pictures. Your program is given two pictures and must decide whether they represent the same image. Geometrically, decide whether the two pictures are similar, that is, whether one can be transformed into the other using only translation, rotation, and uniform scaling (mirroring is not allowed).

Input

The input consists of several test cases, each containing two vector pictures. Each picture is described by a sequence of instructions for a plotter device, one instruction per line. Every instruction begins with a single uppercase letter, followed by one space and two integer coordinates separated by another space. The letter is either "L" (draw a line) or "M" (move without drawing). The two coordinates give the point to which the line is drawn, or to which the current position is moved. Coordinates are always relative to the end position of the previous instruction; the first instruction is relative to some unspecified starting point.

The last instruction of each picture is followed by a line containing only the letter "E" (end) and then an empty line. The last test case is followed by a line containing only the letter "Q" (quit).

The number of instructions in any picture is between 0 and 1000, inclusive. No instruction has both coordinates equal to zero. The absolute value of every (relative) coordinate is at most 1000.

Output

For each test case, print a single line containing "YES" if the two pictures are similar, or "NO" if they are not.

Examples4

  1. Example 1

    Input
    L 3 1
L 3 1
M 3 0
M 0 1
L -3 -1
E

L 1 0
L -1 0
E

L 1 0
L 0 1
E

L 1 0
L -1 -1
E

L 2 0
L 1 1
L 0 1
L 2 3
L 0 1
L -1 1
L -2 0
L -1 -1
L 0 -1
L 2 -3
M 1 0
L -2 0
M 2 0
L 0 -1
L -1 1
L -1 -1
L 0 1
E

L 2 -4
L 3 -1
L 2 1
L 1 -2
L -2 -1
L 1 3
L -3 1
L 2 1
L 1 -2
L 8 -1
L 2 1
L 1 3
L -2 4
L -3 1
L -2 -1
L -4 -7
E

Q
    Expected output
    YES
NO
YES

  2. Example 2

    Input
    L 2 0
E

L 0 5
E

Q
    Expected output
    YES

  3. Example 3

    Input
    L 1 0
L 0 1
L -1 0
L 0 -1
E

L 2 0
L 0 2
L -2 0
L 0 -2
E

L 1 0
L 0 1
L -1 0
L 0 -1
E

L 2 0
L 0 1
L -2 0
L 0 -1
E

Q
    Expected output
    YES
NO

  4. Example 4

    Input
    L 1 0
L 0 1
E

L 1 0
L 0 1
E

Q
    Expected output
    YES