Akshat is analyzing the performance of a Java application that has n threads running on a single-core CPU. Each thread has a unique ID between 0 and n−1.
Since the CPU has only one core, it can execute only one thread at a time, using a thread scheduling stack. When a thread begins execution, its ID is pushed onto the stack, and when it terminates, its ID is popped off the stack. The thread whose ID is at the top of the stack is the currently active thread. The JVM logs each thread's activity, recording the thread ID, whether it started or terminated execution, and the precise millisecond timestamp.
Akshat has a list logEntries, where logEntries[i] represents the ith log message formatted as a string "{thread_id}:{started∣terminated}:{timestamp}". For example, "0:started:3" means thread with ID 0 began execution at the start of millisecond 3, and "1:terminated:2" means thread with ID 1 stopped execution at the end of millisecond 2. Note that a thread can be scheduled multiple times and may also call itself recursively.
A thread's active time is the sum of all milliseconds during which it was the executing thread. For example, if a thread runs twice — one execution lasting for 2 milliseconds and another lasting for 1 millisecond — the active time is 2+1=3.
Help Akshat determine the active time of each thread.
It is given that each thread has a "terminated" log for each "started" log, and only a single thread can be started at a particular time. Also, only a single thread can be terminated at a time. Furthermore, 0≤timestamp≤109.
Input Format:
The first line contains integers n(1≤n≤100000) and m(1≤m≤100000) representing the number of threads and the size of logs.
The following m lines each contain a log. (0≤timestamp≤109)
Output Format:
Give n integers t1,t2,…,tn where ti represents the active time of the thread with ID i.