Problem: Input

The input is given from Standard Input in the following format:


> $N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Output

* You have to print $N$ lines.
* The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.



Constraints

* $3 \le N, Q \le 100,000$
* $1 \le a_i \le N$
* $1 \le b_i \le 10^{12}$
* Any final results do not exceed $2 \times 10^{13}$.



Subtasks

Subtask 1 [ $60$ points ]


* $N, Q \le 100$
* $b_i = 1$

Subtask 2 [ $400$ points ]


* $N, Q \le 100$
* $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]


* $N, Q \le 100,000$
* $b_i = 1$

Subtask 4 [ $500$ points ]


* There are no additional constraints.

Output

* You have to print $N$ lines.
* The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.



Constraints

* $3 \le N, Q \le 100,000$
* $1 \le a_i \le N$
* $1 \le b_i \le 10^{12}$
* Any final results do not exceed $2 \times 10^{13}$.



Subtasks

Subtask 1 [ $60$ points ]


* $N, Q \le 100$
* $b_i = 1$

Subtask 2 [ $400$ points ]


* $N, Q \le 100$
* $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]


* $N, Q \le 100,000$
* $b_i = 1$

Subtask 4 [ $500$ points ]


* There are no additional constraints.

Input

The input is given from Standard Input in the following format:


> $N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Examples

Input

9 3
5 11
8 4
4 7


Output

4
4
4
4
2
2
1
1
0


Input

6 6
3 5
6 11
1 6
4 7
5 2
2 5


Output

10
10
5
5
4
2


Input

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


Output

2
2
1
1
0


Input

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100


Output

223
123
77
50
33
21
12
7
3
1

Solution (in JAVA):

Solution:
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    int N = sc.nextInt();
    int Q = sc.nextInt();
    int[] A = new int[Q];
    long[] B = new long[Q];
    for (int i = 0; i < Q; i++) {
      A[i] = Integer.parseInt(sc.next());
      B[i] = Long.parseLong(sc.next());
    }
    TreeSet<Range> ranges = new TreeSet<>();
    ranges.add(new Range(0, 0));
    ranges.add(new Range(N, -1));
    for (int i = 0; i < Q; i++) {
      Range cur = ranges.lower(new Range(A[i], 0));
      Range next = ranges.higher(cur);
      if (A[i] != next.start) {
        next = new Range(A[i], cur.count);
        ranges.add(next);
      }
      while (true) {
        Range prev = ranges.lower(cur);
        int len = next.start - cur.start;
        if (prev == null || (prev.count - cur.count - 1) * len >= B[i]) {
          cur.count += B[i] / len;
          if (B[i] % len != 0) {
            ranges.add(new Range(cur.start + (int)(B[i] % len), cur.count));
            cur.count++;
          }
          break;
        } else if ((prev.count - cur.count) * len >= B[i]) {
          if (B[i] % len != 0) {
            cur.start += B[i] % len;
            cur.count += B[i] / len;
          } else {
            ranges.remove(cur);
          }
          break;
        } else {
          B[i] -= (prev.count - cur.count) * len;
          ranges.remove(cur);
          cur = prev;
        }
      }
    }
    StringBuilder sb = new StringBuilder();
    ArrayList<Range> rangeList = new ArrayList<>(ranges);
    for (int i = 0; i < rangeList.size() - 1; i++) {
      for (int j = 0; j < rangeList.get(i + 1).start - rangeList.get(i).start; j++) {
        sb.append(rangeList.get(i).count + "\n");
      }
    }
    System.out.print(sb);
  }

  static class Range implements Comparable<Range> {
    int start;
    long count;

    public Range(int start, long count) {
      this.start = start;
      this.count = count;
    }

    @Override
    public int compareTo(Range o) {
      return Integer.compare(this.start, o.start);
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Range range = (Range) o;
      return start == range.start;
    }

    @Override
    public int hashCode() {
      return start;
    }

    @Override
    public String toString() {
      return "Range{" +
          "start=" + start +
          ", count=" + count +
          '}';
    }
  }
}