def recover_bps(delt, bps, bps_star):
    """
    delt, bps, bps_star - seqlen+1 x bsz x K
    returns:
       bsz-length list of lists with (start_idx, end_idx, label) entries
    """
    seqlenp1, bsz, K = delt.size()
    seqlen = seqlenp1 - 1
    seqs = []
    for b in range(bsz):
        seq = []
        _, last_lab = delt[seqlen][b].max(0)
        last_lab = last_lab.item()
        curr_idx = seqlen # 1-indexed
        while True:
            last_len = bps[curr_idx][b][last_lab]
            last_len = int(last_len)
            seq.append((curr_idx-last_len, curr_idx, last_lab)) # start_idx, end_idx, label, 0-idxd

            # print((curr_idx-last_len, curr_idx, last_lab))

            curr_idx -= last_len
            if curr_idx == 0:
                break
            last_lab = bps_star[curr_idx][b][last_lab]
        seqs.append(seq[::-1])
    return seqs