Tần số

Cho một mảng số nguyên \(A\) gồm \(N\) phần tử, đánh số từ \(1\) đến \(N\).
Bạn cần thực hiện \(Q\) truy vấn. Mỗi truy vấn có dạng \((l, r, x, y)\) và được hiểu như sau:

Với mọi chỉ số \(i\) thỏa \(l \le i \le r\):

• nếu \(A[i] = x\) thì gán \(A[i] := y\),
• nếu \(A[i] \ne x\) thì giữ nguyên.

Sau khi thực hiện lần lượt tất cả \(Q\) truy vấn theo đúng thứ tự đã cho, hãy in ra mảng \(A\) cuối cùng.

\InputFile

• Dòng 1 gồm hai số nguyên \(N, Q\) (\(1 \le N, Q \le 2 \cdot 10^5\)).

• Dòng 2 gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 100\)).

• \(Q\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(l, r, x, y\) (\(1 \le l \le r \le N\), \(1 \le x, y \le 100\)).

\OutputFile
In ra \(N\) số nguyên là các phần tử của mảng \(A\) sau khi thực hiện tất cả truy vấn, cách nhau bởi dấu cách.

Example

7 3
1 2 3 2 1 2 3
1 7 2 5
3 6 1 3
1 3 3 2

1 5 2 5 3 5 3