OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题 C: 二分查找(II)

问题 C: 二分查找(II)

时间限制: 1 Sec  内存限制: 128 MB
提交: 1901  解决: 1034
[提交] [状态] [讨论版] [命题人:]

题目描述

对于一个长度为n的有序序列有以下两种操作:
1.对于给定的值x,找到大于等于x的值,如果有多个等于x的值那么就找到最后一个值为x的序列下标,否则就找到第一个大于x的序列下标
2.对于给定的值x,找到小于等于x的值,如果有多个等于x的值那么就找到最后一个值为x的序列下标,否则就找到第一个小于x的序列下标
如果找不到就输出"NO", 序列下标从1开始,序列保证有序。

输入

第一行包含两个正整数n(n <= 100000) 和 m(m <= 100000),分别表示序列大小和询问的次数。第二行是n个由空格隔开的有序序列a(其中0 <= ai <= 200000), 接下来m行每行一个整数x(0 <= x <= 200000)表示要查找的数。

输出

输出包含m行,m行包含两个整数x y, 分别代表第一个和第二个操作的答案,或者找不到就输出"NO"。

样例输入 Copy

5 5
1 3 3 3 5
1
2
3
5
6

样例输出 Copy

1 1
2 1
4 4
5 5
NO 5