Шымкент лицейінде \(n\) жетінші сынып оқушысы оқиды. Бүгін — оларды олимпиадаларға бөлу күні. Лицейде барлығы \(300\) түрлі олимпиада бар, және әр оқушы өзінің келесі 5 жыл бойы дайындалатын олимпиадасына бекітілген. \(i\)-ші оқушының олимпиада нөмірі \(a_i\) деп аталады.

Бірақ кейбір \(m\) топ оқушылар өз олимпиадаларын өзгерте алады. Әр топ төрт бүтін санмен сипатталады: \(l, r, L, R\). Бұл келесіні білдіреді:

> \([l, r]\) аралығындағы әрбір оқушы \(i\), \([L, R]\) аралығындағы кез келген оқушы \(j\)-нің олимпиадасына ауыса алады, яғни \(a_i = a_j\).

Басқаша айтқанда, оқушылар өз олимпиадаларын:

• қалаған ретпен;

• қалағанша көп рет;

• тіпті мүлде өзгертпей де қоя алады.

Барлық мүмкін ауысулардан кейін директорға қызық болды: **әр оқушы қанша түрлі олимпиадаға қатыса алады?**

Сізге әр оқушы \(i\) үшін, барлық мүмкін өзгерістерден кейін \(a_i\) қандай әртүрлі мәндерді қабылдай алатынын анықтау қажет.

Енгізу

Бірінші жолда екі бүтін сан берілген: \(n\) және \(m\) — Шымкент лицейіндегі жетінші сынып оқушыларының саны және өз олимпиадасын өзгерте алатын топтардың саны (\(1 \le n, m \le 100000\)).

Екінші жолда \(n\) бүтін сан берілген: \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 300\)).

Келесі \(m\) жолдың әрқайсысында төрт бүтін сан бар: \(l, r, L, R\) (\(1 \le l \le r \le n\), \(1 \le L \le R \le n\)).

Шығару

\(n\) бүтін санды шығарыңыз: \(b_1, b_2, \dots, b_n\), мұндағы \(b_i\) — кейбір мүмкін ауысулардан кейін оқушы \(i\) қатыса алатын әртүрлі олимпиадалардың саны.

Бағалау жүйесі

Мысалдар

Енгізу 1

4 2
2 2 4 3
4 4 2 4
1 3 2 2

Жауап 1

1 1 2 3

Енгізу 2

6 4
9 5 3 5 1 4
2 4 4 4
5 6 2 2
3 4 2 3
3 4 1 1

Жауап 2

1 3 3 3 4 4