Мендо, заедно со своите пријатели, направил тајна комуникациска мрежа за размена на важни информации. Секој од нив може да испраќа порака, а сите други корисници веднаш ги примаат ново-испратените пораки. Но, ова не е обична мрежа: за сигурност Мендо дефинирал правила кои мора да се почитуваат.

Пред некој да испрати порака, тој мора да ги прочита сите непрочитани пораки коишто до тој момент пристигнале до него (бидејќи тие пораки веднаш се бришат). Кога ќе ја испрати својата порака, испраќачот веднаш си ја чита таа порака, за да провери да не има некоја грешка во текстот на пораката. Секој друг член на групата ја добива ново-испратената порака, но таа ќе биде непрочитана за нив се додека тие самите не испратат некоја нова порака.

Мендо сака да знае колку непрочитани пораки се присутни во мрежата по секоја нова-испратена порака. Помогнете му на Мендо, и следете ја состојбата на непрочитаните пораки.

Влез

Првата линија содржи два цели броеви N (1 ≤ N ≤ 10⁹) и M (1 ≤ M ≤ 10⁵) - бројот на корисници на мрежата и бројот на пораки.

Следните M линии содржат по еден цел број X_i (1 ≤ X_i ≤ N) - испраќачот на i-тата порака.

Забелешка. За 60% од поените важи: N ≤ 1000, M ≤ 1000.

Излез

Отпечатете M броеви, секој во различен ред - секој број треба да означува колку непрочитани пораки има во моментот откако е испратена пораката од корисникот X_i.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5 4
1
2
1
3

излез
4
7
10
11