Problem: 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 ≤q N ≤q 10^{12}  
1 ≤q Q ≤q 10^5  
1 ≤q F ≤q N  
1 ≤q K ≤q 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.

SAMPLE INPUT
10 2
1 2 3
2 6 2

SAMPLE OUTPUT
1 3

Explanation

Initially the elevator is at floor 1 with no people inside. The first event is an entry event at floor 2 with 3 people wanting to enter the elevator. Is is a possible event, because 2 + 3 = 5 is a prime number, so the elevator must go to the 2nd floor to handle this event. However, the second event is not possible, because it is an exit event and 6 + 2 = 8 has 4 divisors, which is an even number. Finally, the elevator must handle only the first event, and the minimal distance it need to cover to do that is 1 and the number of people after handling this event inside the elevator is 3.

Solution (in PYTHON):

Solution:
def check_composite(n, s, d, a):
    '''
   check compositeness of n with witness a
   (n,s,d) should satisfy d*2^s = n-1 and d is odd
   '''
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return False
    for y in xrange(1, s):
        x = x * x % n
        if x == 1:
            return True
        if x == n - 1:
            return False
    return True
small_primes = set([3,5,7,11,13,17,19,23,29,31,37])
small_is_prime = [s in small_primes for s in xrange(38)]
small_is_prime[2] = True
 
# witnesses for different bounds (taken from http://miller-rabin.appspot.com/ )
witnesses_bounds = [
    (341531, [9345883071009581737]),
    (716169301, [15, 13393019396194701]),
    (154639673381, [15, 176006322, 4221622697]),
    (47636622961201, [2, 2570940, 211991001, 3749873356]),
    (3770579582154547, [2, 2570940, 880937, 610386380, 4130785767]),
]
# set of witnesses for < 2^64 (taken from http://miller-rabin.appspot.com/ )
i64_witnesses = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
def is_prime(n):
    '''
   returns True if n is probably prime, and False if n is definitely not prime.
   if n < 2^64, then is_prime(n) never returns a wrong answer.
   '''
    # if too small, check small_is_prime
    if n < 38:
        return small_is_prime[n]
    # check divisibility with small primes
    for s in small_primes:
        if n % s == 0:
            return False
    # find (d,s) such that d*2^s = n-1 with d odd
    d = n - 1
    s = 0
    while not d & 1:
        d >>= 1
        s += 1
    # find the best set of witnesses
    best_witnesses = i64_witnesses
    for bound, bound_ws in witnesses_bounds:
        if n < bound:
            best_witnesses = bound_ws
            break
    # check compositeness with the witnesses
    for a in best_witnesses:
        a %= n
        if a and check_composite(n, s, d, a):
            return False
    return True
#########################################################
N = 10**12
Q = 10**5
K = 10**6
M = 10**9 + 7
MAX_X = N + K
squares = set()
i = 1
while i * i <= MAX_X:
    squares.add(i * i)
    i += 1
def is_square(x):
    return x in squares
n, q = map(int, raw_input().split())
assert(n >= 1 and n <= N)
assert(q >= 1 and q <= Q)
res = 0
cur_p = 0
cur_f = 1
for _ in xrange(q):
    t, f, k = map(int, raw_input().split())
    assert(t in [1,2])
    assert(f >= 1 and f <= n)
    assert(k <= K);
    assert(k >= 1 and (t == 1 or k <= cur_p))
    if t == 1:
        if is_prime(f + k):
            res += abs(cur_f - f)
            res %= M
            cur_p += k
            cur_f = f
    elif t == 2:
        if is_square(f + k):
            res += abs(cur_f - f)
            res %= M
            cur_p -= k
            cur_f = f
print res, cur_p