Бүтін \(n\) саны берілген. \(n \times n\) өлшемді квадрат кесте құру қажет, онда әрбір ұяшықта төрт әріптің бірі жазылуы тиіс:

• U — жоғары қозғалу

• D — төмен қозғалу

• L — солға қозғалу

• R — оңға қозғалу

Кестенің жолдары жоғарыдан төмен қарай \(1\)-ден \(n\)-ге дейін, ал бағандары солдан оңға қарай \(1\)-ден \(n\)-ге дейін нөмірленеді.

Әрбір ұяшық көрші ұяшыққа өту бағытын көрсетеді. Кестенің шекарасынан шығуға тыйым салынады, яғни барлық бағыттар кестенің ішінде қалуы керек.

Сондай-ақ, бүтін сан \(m\) және \(m\) жұп ұяшықтар \((x_1, y_1, x_2, y_2)\) берілген. Онда келесі шарт орындалатындай кесте құру қажет:

• \((x_1, y_1)\) ұяшығынан \((x_2, y_2)\) ұяшығына немесе керісінше — \((x_2, y_2)\)-ден \((x_1, y_1)\)-ге бағыттар бойынша жетуге болады.

• Бұл жұпта екі бағытта да бір уақытта жетуге мүмкіндік болу міндетті емес.

Кез келген дұрыс кестені табыңыз.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(m\) \((2 \le n \le 20, 1 \le m \le 1000)\) беріледі.

Келесі \(m\) жолдың әрқайсысы төрт бүтін саннан тұрады: \(x_1, y_1, x_2, y_2\) \((1 \le x_1, x_2, y_1, y_2 \le n)\). Жұптар қайталануы мүмкін. Әрбір ұяшық бірнеше жұптың құрамында болуы мүмкін.

Шығару

Әрқайсысында \(n\) әріп болатын \(n\) жолдан тұратын бағыттар кестесін шығарыңыз.

Кем дегенде бір дұрыс шешімнің әрқашан бар екендігіне кепілдік беріледі.

Мысалдар

Енгізу 1

3 2
1 1 2 2
1 3 3 3

Жауап 1

RDL
RDL
URU