View Russian Translation

In this problem the goal is to implement a program managing an elevator designed especially for mathematicians.

The elevator can go to any of N floors numbered from 1 to N and it can carry an arbitrary number of people at one time.

Initially the elevator is at floor 1, without any people inside, and it can go to any floor from 1 to N at any time. The total distance the elevator travels is defined as the sum of distances between the consecutive floors it went to in the whole process, and the distance between two floors \(F_1\) and \(F_2\) is defined as \(|F_1 - F_2|\).

In addition, there are Q events which are about to happen consecutively starting from now. There are two types of events to handle:

• \(entry(F, K)\) - K people are waiting to enter the elevator at floor F
• \(exit(F, K)\) - K people are waiting to exit the elevator at floor F

The elevator must handle events in the order they come, and must handle only the events which are possible.

An entry event \(entry(F, K)\) is possible if and only if \(X = F + K\) is a prime number.

An exit event \(exit(F, K)\) is possible if and only if \(X = F + K\) has odd number of divisors.

If the elevator being currently on floor \(F_1\) has to handle an event taking place on floor \(F_2\), it must first go from floor \(F_1\) to floor \(F_2\) moving up and/or down in any possible way, and it can handle the event only while it is at floor \(F_2\).

The task in this problem is to print the minimum distance that the elevator has to travel to handle all possible events in the order they come and the number of people inside the elevator after handling the last possible event. Since the total distance can be very large, output it modulo \(10^9 + 7\).

Constraints:

• \(1 \leq N \leq 10^{12}\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq F \leq N\)
• \(1 \leq K \leq 10^6\)
• for an exit event \(exit(F, K)\), parameter K is not greater than the number of people in the elevator just before that event

Input format:

In the first line there are two integers N and Q denoting the number of floors and the number of events. In the following Q lines the descriptions of Q events in the order they come are given. Each single event is given by 3 space separated integers \(T, F, K\), where T is either 1 or 2 and denotes the type of the event (1 stands for an entry event, 2 stands for an exit event), F denotes the number of floor where this event has to be handled if it is a possible event, and K denotes the number of people in this event.

Output format:

In a single line output two space separated integers \(D, K\) denoting the minimum total distance the elevator travels to handle all possible events taken modulo \(10^9 + 7\), and the number of people in the elevator after the last handled event.