Програмчлалын олимпиадын бодлогын архив

“Хуваалт” тоглоомыг тоглоход тойрог хэлбэрээр тавьсан хайрцгууд ба тэдгээрт байх бөмбөлгүүдийг ашиглана. Нүүдлийг дараах байдлаар гүйцэтгэнэ.

Аль нэг хайрцагт байгаа бүх бөмбөлгийг авч цагийн зүүний дагуу дараагийн хайрцагнаас эхлэн нэг нэгээр нь тарааж хийнэ. Хэрэв бөмбөлгийн тоо хайрцагны тооноос олон бол бөмбөлгүүдийг дуустал нь цааш үргэлжлүүлэн (хоёр дахь болон гурав дахь удаагаа тойруулах гэх мэтээр) тараана. Анх бөмбөлгүүдийг авсан хайрцагт ч мөн адил бөмбөлөг хийнэ. Доорх зураг дээр нэг нүүдлийг дүрслэн үзүүлэв. Баруун талд бөмбөлгүүдийг хайрцагт хийсэн дарааллыг хажууд нь бичсэн.

Нэгэн тоглогч хайрцгуудад бөмбөлгүүдийг тараан хийснийхээ дараа хэд хэдэн нүүдэл хийжээ. Тэр нүүдэл болгоныхоо дараа хамгийн сүүлийн бөмбөлгийг хийсэн хайрцагны дугаарыг бичиж байсан. Дараа нь одоо байгаа байрлалаасаа бичиж авсан хайрцагны дугааруудаа ашиглан анхны байрлалыг гаргаж авахыг хүсчээ. Үүнд нь туслах програмыг бичнэ үү.

Input

Эхний мөрөнд хайрцагны тоо болох N, хийсэн нүүдлийн тоо болох M гэсэн хоёр натурал тоо өгөгдөнө (N ≤ 100, M ≤ 100). Хайрцгууд цагийн зүүний дагуу 1-ээс N хүртлэх тоонуудаар дугаарлагдана.

Дараагийн N тооны мөр тус бүрт нүүдлүүдийг хийсний эцэст 1-р, 2-р, ..., N-р хайрцганд байсан бөмбөлгүүдийн тоо өгөгдөнө.

Дараагийн M тооны мөр тус бүрт 1-р, 2-р, ..., M-р нүүдлийн хамгийн сүүлийн бөмбөлгийг хийсэн хайрцагны дугаар байрлана. Бөмбөлгийн нийт тоо 10⁹ – ээс хэтрэхгүй.

Output

N тооны мөр тус бүрт 1-р, 2-р, ..., N-р хайрцагт анх байсан бөмбөлгийн тоог хэвлэнэ.

Example

Input:
4 1
1
2
2
2
4

Output:
7
0
0
0