Little Artem is fond of dancing. Most of all dances Artem likes rueda — Cuban dance that is danced by pairs of boys and girls forming a circle and dancing together.

More detailed, there are n pairs of boys and girls standing in a circle. Initially, boy number 1 dances with a girl number 1, boy number 2 dances with a girl number 2 and so on. Girls are numbered in the clockwise order. During the dance different moves are announced and all pairs perform this moves. While performing moves boys move along the circle, while girls always stay at their initial position. For the purpose of this problem we consider two different types of moves:

  1. Value x and some direction are announced, and all boys move x positions in the corresponding direction. 
  2. Boys dancing with even-indexed girls swap positions with boys who are dancing with odd-indexed girls. That is the one who was dancing with the girl 1 swaps with the one who was dancing with the girl number 2, while the one who was dancing with girl number 3 swaps with the one who was dancing with the girl number 4 and so one. It's guaranteed that n is even. 



Your task is to determine the final position of each boy.

Input

The first line of the input contains two integers n and q (2 ≤ n ≤ 1 000 000, 1 ≤ q ≤ 2 000 000) — the number of couples in the rueda and the number of commands to perform, respectively. It's guaranteed that n is even.

Next q lines contain the descriptions of the commands. Each command has type as the integer 1 or 2 first. Command of the first type is given as x ( - n ≤ x ≤ n), where 0 ≤ x ≤ n means all boys moves x girls in clockwise direction, while  - x means all boys move x positions in counter-clockwise direction. There is no other input for commands of the second type.

Output

Output n integers, the i-th of them should be equal to the index of boy the i-th girl is dancing with after performing all q moves.

Examples

Input

6 3
1 2
2
1 2


Output

4 3 6 5 2 1


Input

2 3
1 1
2
1 -2


Output

1 2


Input

4 2
2
1 3


Output

1 4 3 2
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private final InputReader in;
    private final PrintWriter out;

    public Main(final InputReader in, final PrintWriter out) {
        this.in = in;
        this.out = out;
    }

    private static PrintWriter getOutput(final String filename) throws IOException {
        if (filename == null || filename.isEmpty()) {
            return new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            return new PrintWriter(new FileWriter(filename + ".out"));
        }
    }

    public static void main(final String[] args) throws NumberFormatException, IOException {
        final String filename = "";
        final long time = System.currentTimeMillis();
        try (final InputReader in = new InputReader(filename); final PrintWriter out = getOutput(filename)) {
            new Main(in, out).solve();
        }
//        System.err.println("Running time: " + (System.currentTimeMillis() - time));
    }

    private void swap(final int[] t) {
        int temp = t[0];
        t[0] = t[1];
        t[1] = temp;
    }

    private void bf(final int[] a, final int c, final int d, final int n) {
        switch (c) {
            case 1:
                final int[] result = new int[n + 1];
                for (int i = 1; i <= n; i++) {
                    int j = (i + d + n) % n;
                    if (j == 0) j = n;
                    result[j] = a[i];
                }

                System.arraycopy(result, 1, a, 1, n);
                break;
            case 2:
                for (int i = 1; i <= n; i += 2) {
                    final int t = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = t;
                }
                break;
        }
    }

    public void solve() throws NumberFormatException, IOException {
        final int n = in.nextInt();
        final int q = in.nextInt();

        int start = 1;
        final int[] d = {1, 1};
        final int[] change = {-2, +2};

        final int[] t = new int[n + 1];
        for (int i = 1; i <= n; i++) t[i] = i;

        for (int i = 0; i < q; i++) {
            int command = in.nextInt();
            int shift = 0;
            switch (command) {
                case 1:
                    shift = in.nextInt();
                    shift = (shift + n) % n;
                    start = (start + shift + n) % n;
                    if (start == 0) start = n;
                    if (shift % 2 == 1) swap(change);
                    break;
                case 2:
                    if (start % 2 == 1) start++;
                    else start--;
                    d[0] = (d[0] + change[0] + n) % n;
                    if (d[0] == 0) d[0] = n;
                    d[1] = (d[1] + change[1] + n) % n;
                    if (d[1] == 0) d[1] = n;
                    swap(change);
                    break;
            }
//            final int[] result = getResult(n, start, d);
//            bf(t, command, shift, n);
//            out.println(Arrays.toString(result));
//            out.println(Arrays.toString(t));
            //assertTrue(Arrays.equals(result, t));
        }

        final int[] result = getResult(n, start, d);
        for (int i = 1; i <= n; i++) {
            out.print(result[i]);
            out.print(' ');
        }
        out.println();
    }

    private int[] getResult(int n, int start, int[] d) {
        final int[] result = new int[n + 1];
        result[start] = 1;
        for (int i = 2, prev = start; i <= n; i++) {
            int nextIndex = (prev + d[i % 2]) % n;
            if (nextIndex == 0) nextIndex = n;
            result[nextIndex] = i;
            prev = nextIndex;
        }
        return result;
    }

    private void assertTrue(final boolean t) {
        if (!t) throw new RuntimeException();
    }
}

class InputReader implements Closeable {
    private StringTokenizer st;
    private final BufferedReader in;

    public InputReader(final String filename) throws IOException {
        if (filename == null || filename.isEmpty())
            in = new BufferedReader(new InputStreamReader(System.in));
        else
            in = new BufferedReader(new FileReader(filename + ".in"));
    }

    public boolean hasNextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null)
                return false;
            st = new StringTokenizer(line);
        }
        return true;
    }

    public String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null)
                return null;
            st = new StringTokenizer(line);
        }
        return st.nextToken();
    }

    public String readLine() throws IOException {
        return in.readLine();
    }

    public int nextInt() throws NumberFormatException, IOException {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws NumberFormatException, IOException {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(nextToken());
    }

    @Override
    public void close() throws IOException {
        in.close();
    }
}