Problem: Vasya likes to travel by train, but doesn't like when the car he travels in is located in the tail of the train.

Vasya gets on the train at the station. The train consists of n cars indexed from 1 to n counting from the locomotive (head of the train). Three types of events occur while the train is moving:

  1. Some number of cars are added to the head of the train; 
  2. Some number of cars are added to the tail of the train; 
  3. Vasya recalculates the values of the convenience of the cars (read more about it below). 



At each moment of time we will index the cars from the head of the train, starting from 1. Note that when adding new cars to the head of the train, the indexing of the old ones may shift.

To choose which car to go in, Vasya will use the value A_i for each car (where i is a car index), which is calculated as follows:

  * At the beginning of the trip A_i=0, as well as for the new cars at the time of their addition. 
  * During the next recalculation Vasya chooses some positive integers b and s and adds to all A_i value b + (i - 1) ⋅ s. 



Vasya hasn't decided yet where he will get on the train and where will get off the train, so after each event of one of the three types he wants to know the least index of the car, such that its value A_i is minimal. Since there is a lot of cars, Vasya asked you to write a program that answers his question.

Input

The first line contains two integers n and m (1 ≤ n ≤ 10^9, 1 ≤ m ≤ 300 000), the number of cars in the train at the time of departure from the station and the number of stations, respectively.

Next m lines contain the descriptions of events. Each event is one of the following three types:

  * "1 k" (1 ≤ k ≤ 10^9), add k cars to the head of the train 
  * "2 k" (1 ≤ k ≤ 10^9), add k cars to the tail of the train 
  * "3 b s" (1 ≤ b, s ≤ 10^9), recalculate the convenience of all train cars. 



It is guaranteed that at any time the train length does not exceed 10^9. Also it's guaranteed that the integers A_i will not grow too high. Formally, it's guaranteed that if we sum the largest addition over all events of the 3-rd type (that is, b + (n - 1) ⋅ s, where n is the number of cars at that moment) then the acquired sum would be at most 10^{18}.

Output

After each of the m queries print two integers: j and A_j — the number of the car closest to the head of the train, such that its value A_j is minimal, and the value A_j itself.

Example

Input


1 8
1 1
3 1 1
3 1 1
2 1
2 1
3 1 1
2 1
3 1 5


Output


1 0
1 1
1 2
3 0
3 0
1 3
5 0
1 4

Note

  * Initially the train consists of one car with A_1 = 0, let's denote train as [0] for simplicity.
  * After adding one car to the head, train is [0, 0].
  * After recalculation of values with parameters b=1, s=1, train is [1, 2].
  * After another recalculation of values with the parameters b=1, s=1, train is [2, 4].
  * After adding one car to the end, train is [2, 4, 0].
  * After another adding one car to the end, train is [2, 4, 0, 0].
  * After recalculation of values with parameters b=1, s=1, train is [3, 6, 3, 4].
  * After adding one car to the end, train is [3, 6, 3, 4, 0].
  * After recalculation of values with parameters b=1, s=5, train is [4, 12, 14, 20, 21].

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Iterator;
import java.util.HashMap;
import java.io.IOException;
import java.util.TreeSet;
import java.io.UncheckedIOException;
import java.util.Map;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            ETrainCarSelection solver = new ETrainCarSelection();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class ETrainCarSelection {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int m = in.readInt();

            LongConvexHullTrick cht = new LongConvexHullTrick();
            int l = 1;
            int r = n;
            Map<LongConvexHullTrick.Line, Integer> map = new HashMap<>(m + 1);
            map.put(cht.insert(0, 0), 1);
            long bSum = 0;
            long sSum = 0;
            for (int i = 0; i < m; i++) {
                int t = in.readInt();
                if (t == 1) {
                    int k = in.readInt();
                    cht.clear();
                    map.put(cht.insert(0, 0), l - k);
                    bSum = sSum = 0;
                    l -= k;
                } else if (t == 2) {
                    int k = in.readInt();
                    //size * sSum + b + bSum = 0
                    // b = -bSum - size * sSum
                    int size = r - l + 1;
                    map.put(cht.insert(-size, -(-bSum - size * sSum)), r + 1);
                    r += k;
                } else {
                    bSum += in.readInt();
                    sSum += in.readInt();
                }

                LongConvexHullTrick.Line line = cht.queryLine(sSum);
                long ans = -line.y(sSum) + bSum;
                out.append(map.get(line) - l + 1).append(' ').append(ans).println();
            }
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static long floorDiv(long a, long b) {
            return a < 0 ? -ceilDiv(-a, b) : a / b;
        }

        public static long ceilDiv(long a, long b) {
            if (a < 0) {
                return -floorDiv(-a, b);
            }
            long c = a / b;
            if (c * b < a) {
                return c + 1;
            }
            return c;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            return this;
        }

        public FastOutput println() {
            cache.append('\n');
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class LongConvexHullTrick implements Iterable<LongConvexHullTrick.Line> {
        static final long INF = (long) 2e18;
        TreeSet<LongConvexHullTrick.Line> setSortedByA = new TreeSet<>(LongConvexHullTrick.Line.sortByA);
        TreeSet<LongConvexHullTrick.Line> setSortedByL = new TreeSet<>(LongConvexHullTrick.Line.sortByL);
        private LongConvexHullTrick.Line qBody = new LongConvexHullTrick.Line(0, 0);

        private long rightBoundOfXPrefX(LongConvexHullTrick.Line x, LongConvexHullTrick.Line y) {
            //x.a * r + x.b >= y.a * r + y.b
            //x.a * (r + 1) + x.b < y.a * (r + 1) + y.b
            //r * (y.a - x.a) <= x.b - y.b
            //r <= (x.b - y.b) / (y.a - x.a)
            return (x.b - y.b) / (y.a - x.a);
        }

        private long rightBoundOfXPrefY(LongConvexHullTrick.Line x, LongConvexHullTrick.Line y) {
            return DigitUtils.floorDiv(x.b - y.b - 1, y.a - x.a);
        }

        private void removeLine(LongConvexHullTrick.Line line) {
            setSortedByA.remove(line);
            setSortedByL.remove(line);
        }

        private void addLine(LongConvexHullTrick.Line line) {
            setSortedByA.add(line);
            setSortedByL.add(line);
        }

        public LongConvexHullTrick.Line queryLine(long x) {
            qBody.l = x;
            return setSortedByL.floor(qBody);
        }

        public LongConvexHullTrick.Line insert(long a, long b) {
            LongConvexHullTrick.Line line = new LongConvexHullTrick.Line(a, b);

            while (true) {
                LongConvexHullTrick.Line floor = setSortedByA.floor(line);
                if (floor == null) {
                    line.l = -INF;
                    break;
                }
                if (floor.a == line.a) {
                    if (floor.b >= line.b) {
                        return line;
                    } else {
                        removeLine(floor);
                        continue;
                    }
                }

                long r = rightBoundOfXPrefX(floor, line);
                if (r > floor.r + 1) {
                    return line;
                }
                if (r < floor.l) {
                    setSortedByA.remove(floor);
                    continue;
                }
                floor.r = r;
                line.l = r + 1;
                break;
            }

            while (true) {
                LongConvexHullTrick.Line ceil = setSortedByA.ceiling(line);
                if (ceil == null) {
                    line.r = INF;
                    break;
                }
                long r = rightBoundOfXPrefY(line, ceil);
                if (r < ceil.l - 1) {
                    return line;
                }
                removeLine(ceil);
                if (r >= ceil.r) {
                    continue;
                }
                ceil.l = r + 1;
                line.r = r;
                addLine(ceil);
                break;
            }

            if (!line.isEmpty()) {
                addLine(line);
            }
            return line;
        }

        public void clear() {
            setSortedByL.clear();
            setSortedByA.clear();
        }

        public Iterator<LongConvexHullTrick.Line> iterator() {
            return setSortedByA.iterator();
        }

        public static class Line {
            long a;
            long b;
            long l;
            long r;
            static Comparator<LongConvexHullTrick.Line> sortByA = (x, y) -> Long.compare(x.a, y.a);
            static Comparator<LongConvexHullTrick.Line> sortByL = (x, y) -> Long.compare(x.l, y.l);

            public Line(long a, long b) {
                this.a = a;
                this.b = b;
            }

            public long y(long x) {
                return a * x + b;
            }

            public boolean isEmpty() {
                return r < l;
            }

        }

    }
}