This is a simplified version of the task Toy Train. These two versions differ only in the constraints. Hacks for this version are disabled.

Alice received a set of Toy Train™ from Bob. It consists of one train and a connected railway network of n stations, enumerated from 1 through n. The train occupies one station at a time and travels around the network of stations in a circular manner. More precisely, the immediate station that the train will visit after station i is station i+1 if 1 ≤ i < n or station 1 if i = n. It takes the train 1 second to travel to its next station as described.

Bob gave Alice a fun task before he left: to deliver m candies that are initially at some stations to their independent destinations using the train. The candies are enumerated from 1 through m. Candy i (1 ≤ i ≤ m), now at station a_i, should be delivered to station b_i (a_i ≠ b_i).

<image> The blue numbers on the candies correspond to b_i values. The image corresponds to the 1-st example.

The train has infinite capacity, and it is possible to load off any number of candies at a station. However, only at most one candy can be loaded from a station onto the train before it leaves the station. You can choose any candy at this station. The time it takes to move the candies is negligible.

Now, Alice wonders how much time is needed for the train to deliver all candies. Your task is to find, for each station, the minimum time the train would need to deliver all the candies were it to start from there.

Input

The first line contains two space-separated integers n and m (2 ≤ n ≤ 100; 1 ≤ m ≤ 200) — the number of stations and the number of candies, respectively.

The i-th of the following m lines contains two space-separated integers a_i and b_i (1 ≤ a_i, b_i ≤ n; a_i ≠ b_i) — the station that initially contains candy i and the destination station of the candy, respectively.

Output

In the first and only line, print n space-separated integers, the i-th of which is the minimum time, in seconds, the train would need to deliver all the candies were it to start from station i.

Examples

Input


5 7
2 4
5 1
2 3
3 4
4 1
5 3
3 5


Output


10 9 10 10 9 


Input


2 3
1 2
1 2
1 2


Output


5 6 

Note

Consider the second sample.

If the train started at station 1, the optimal strategy is as follows.

  1. Load the first candy onto the train. 
  2. Proceed to station 2. This step takes 1 second. 
  3. Deliver the first candy. 
  4. Proceed to station 1. This step takes 1 second. 
  5. Load the second candy onto the train. 
  6. Proceed to station 2. This step takes 1 second. 
  7. Deliver the second candy. 
  8. Proceed to station 1. This step takes 1 second. 
  9. Load the third candy onto the train. 
  10. Proceed to station 2. This step takes 1 second. 
  11. Deliver the third candy. 



Hence, the train needs 5 seconds to complete the tasks.

If the train were to start at station 2, however, it would need to move to station 1 before it could load the first candy, which would take one additional second. Thus, the answer in this scenario is 5+1 = 6 seconds.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * #
 *
 * @author pttrung
 */
public class A1_Round_542_Div1 {

    public static long MOD = 998244353;
    static long[][][] dp;

    public static void main(String[] args) throws FileNotFoundException {
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
        // "output.txt")));
        PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner();
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] data = new int[m][2];
        ArrayList<Integer>[] q = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            q[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 2; j++) {
                data[i][j] = in.nextInt() - 1;
            }
            q[data[i][0]].add(data[i][1]);
        }
        for (int i = 0; i < n; i++) {
            final int v = i;
            Collections.sort(q[i], (a, b) -> {
                int x = (a - v + n) % n;
                int y = (b - v + n) % n;
                return Integer.compare(x, y);
            });
            //System.out.println(q[i]);
        }
        for (int i = 0; i < n; i++) {
            int left = m;
            int[] tmp = new int[n];
            int re = 0;
            int[] count = new int[n];
            int st = i;
            //System.out.println("Start");
            while (left > 0) {
                int index = i;
                if (st != i) {
                    re += (i - st + n) % n;
                    st = i;
                }
                for (int j = 0; j < n; j++) {
                    if (tmp[index] < q[index].size()) {
                        int k = q[index].size();
                        int v = q[index].get(k - tmp[index] - 1);
                        count[v]++;
                        tmp[index]++;
                        re += (index - st + n) % n;
                        st = index;
                    }
                    if (count[index] > 0) {
                        left -= count[index];
                        re += (index - st + n) % n;
                        st = index;
                    }
                    count[index] = 0;
                    index = (index + 1) % n;
                }

            }
            out.print(re + " ");
        }
        out.close();
    }


    public static int[] KMP(String val) {
        int i = 0;
        int j = -1;
        int[] result = new int[val.length() + 1];
        result[0] = -1;
        while (i < val.length()) {
            while (j >= 0 && val.charAt(j) != val.charAt(i)) {
                j = result[j];
            }
            j++;
            i++;
            result[i] = j;
        }
        return result;

    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static int digit(long n) {
        int result = 0;
        while (n > 0) {
            n /= 10;
            result++;
        }
        return result;
    }

    public static double dist(long a, long b, long x, long y) {
        double val = (b - a) * (b - a) + (x - y) * (x - y);
        val = Math.sqrt(val);
        double other = x * x + a * a;
        other = Math.sqrt(other);
        return val + other;

    }

    public static class Point implements Comparable<Point> {

        int x, y;

        public Point(int start, int end) {
            this.x = start;
            this.y = end;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 47 * hash + this.x;
            hash = 47 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }

        @Override
        public int compareTo(Point o) {
            return Integer.compare(x, o.x);
        }
    }

    public static class FT {

        long[] data;

        FT(int n) {
            data = new long[n];
        }

        public void update(int index, long value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public long get(int index) {
            long result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long pow(long a, long b, long MOD) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2, MOD);
        if (b % 2 == 0) {
            return val * val % MOD;
        } else {
            return val * (val * a % MOD) % MOD;

        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //  br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt"))));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}