def cutlabel(s, cuts):
    """Cuts a string s using a set of (n, label) cuts.
    Returns a list of (sub, label) pairs.
    If there was an initial part before the first cut, then it has a label of None.
    If there are no cuts, returns s as a single element, with label None.
    """
    cuts = sorted(cuts)
    # no cuts -> whole string is an element
    if not cuts: return [(s, None)]
    if cuts[0][0] != 0:
        cuts.insert(0, (0, None))
    if cuts[-1][0] < len(s)-1:
        cuts.append((len(s), None))
    locs, labels = zip(*cuts)
    ret = []
    for i, j, label in zip(locs, locs[1:], labels):
        ret.append((s[i:j], label))
    return ret