import random
import sys

seed = int(sys.argv[1])
random.seed(seed)

n = int(sys.argv[2])
m = int(sys.argv[3])

kid_pref_type = sys.argv[4]
assert kid_pref_type in ['random', 'all-same']
toy_pref_type = sys.argv[5]
assert toy_pref_type in ['random-allow-ties', 'random-no-ties',
                         'all-same', 'all-same-decreasing']
                     

def encode_preferences(kid_pref, toy_pref_dur):
    # Uses almost (n+1)*m events.  Attempts to compress times somewhat.
    #
    # kid_pref[k][j] is j'th most preferred toy for kid k
    # toy_pref_dur[t][k] is desired total length that kid k plays with toy t
    n = len(kid_pref)
    m = len(toy_pref_dur)

    kids = range(n)
    random.shuffle(kids)

    E = []
    pending_stops = {}
    avail_from = [0]*m
    kid_scheds = []
    for k in kids:
        kid_sched = []
        cur_d = 0
        min_shift = 0
        for j in range(m):
            t = kid_pref[k][j]
            d = toy_pref_dur[t][k]
            min_shift = max(min_shift, avail_from[t] - cur_d)
            kid_sched.append((cur_d, t))
            cur_d += d
        for (s, t) in kid_sched:
            if t in pending_stops:
                (other_kid, stop_time) = pending_stops[t]
                E.append((stop_time, other_kid+1, 0))
                del pending_stops[t]
            E.append((s+min_shift, k+1, t+1))
            avail_from[t] = s+min_shift+toy_pref_dur[t][k]
        pending_stops[t] = (k, cur_d+min_shift)

    endt = max(st for (_, st) in pending_stops.values())
    for (t, (k, st)) in pending_stops.items():
        if st != endt:
            E.append((st, k+1, t+1))
        
    return (endt, sorted(E))


def rand_perm(S):
    ret = [s for s in S]
    random.shuffle(ret)
    return ret

def gen_kid_pref(n, m, typ):
    if typ == 'random':
        return [rand_perm(range(m)) for _ in range(n)]
    elif typ == 'all-same':
        p = rand_perm(range(m))
        return [p for _ in range(n)]
    else:
        assert False

def gen_toy_pref_dur(n, m, typ):
    if typ == 'random-no-ties':
        return [rand_perm(range(1, n+1)) for _ in range(m)]
    elif typ == 'random-allow-ties':
        return [[random.randint(1, n) for _ in range(n)] for _ in range(m)]
    elif typ == 'all-same':
        p = rand_perm(range(1, n+1))
        return [p for _ in range(m)]
    elif typ == 'all-same-decreasing':
        return [range(n, 0, -1) for _ in range(m)]
    else:
        assert False
    
def gen_case(n, m, kid_pref_type, toy_pref_type):
    kid_pref = gen_kid_pref(n, m, kid_pref_type)
    toy_pref_dur = gen_toy_pref_dur(n, m, toy_pref_type)

    (b, E) = encode_preferences(kid_pref, toy_pref_dur)
    
    print '%d %d' % (n, m)
    print '%d %d' % (b, len(E))
    for (s, k, t) in E:
        print s, k, t

gen_case(n, m, kid_pref_type, toy_pref_type)