def parse_data(input_str: str) -> tuple:
    """
    解析输入的数据
    Args:
        input_str (str):输入的数据
    Returns:
        N, K, sentences
    """
    line_list = input_str.strip().split('\n')
    sentences = []
    n, k = 0, 0
    for line in line_list:
        line = line.strip()
        if not line:
            continue
        temp_ls = line.split(' ')
        if len(temp_ls) == 2:
            n, k = int(temp_ls[0]), int(temp_ls[1])
        else:
            sentences.append([int(i) for i in temp_ls])
    return n, k, sentences