Description

给定一些日期区段，针对休假天数找满足要求的最短日期区段。

Input

第一个整数N，表示后面有N组数据。每组数据第一个整数表示休假天数，后跟一个整数表示有M个日期区段，日期区段由两个格式为“YYYY-MM-DD”的日期构成。

Output

输出符合要求的起始日期。

Sample

Input

1
3
4
2006-04-09  2006-04-10
2006-03-26  2006-04-03
2006-04-16  2006-04-20
2006-03-01  2006-03-16

Output

2006-04-16