B. 浇花

内存限制:256 MiB 时间限制:1000 ms 输入文件: jiao.in 输出文件: jiao.out
题目类型:传统 评测方式:文本比较

题目描述

某公司养有观赏花,这些花十分娇贵,每天都需要且仅需要浇水一次。

如果某一天没给花浇水或者给花浇水超过一次,花就会在那一天死亡。

公司即将迎来 n 天假期,编号 1∼n

为了让花能够活过整个假期,公司领导安排了 m 个人(编号 1∼m )来公司浇花,其中第 i 个人在第 [a_i, b_i] 天每天来公司浇一次花。

领导是按照时间顺序安排的浇花任务,保证了对于 1≤i≤m−1 ,均满足: a_i<=a_{i+1}

给定领导的具体安排,请你判断,花能否活过整个假期,如果不能,请你输出它是在第几天死的,以及那一天的具体浇水次数。

输入格式

第一行包含两个整数 n , m

接下来 m 行,每行包含两个整数 a_i, b_i

输出格式

输出一行结果。

如果花能活过整个假期,则输出 OK。

如果花不能活过整个假期,则输出两个整数 x,y ,表示花是在第 x 天死的,这一天花被浇了 y 次水。

样例

输入样例1:

10 5
1 2
3 3
4 6
7 7
8 10

输出样例1:

OK

输入样例2:

10 5
1 2
2 3
4 5
7 8
9 10

输出样例2:

2 2

输入样例3:

10 5
1 2
3 3
5 7
7 7
7 10

输出样例3:

4 0

数据范围与提示

前 4 个测试点满足 1≤n,m≤10

所有测试点满足 1≤n,m≤10^5,1≤a_i≤b_i≤n