Given two lists of numbers, the numbers in the first list are in non-descending order. For each number in the second list, determine the number of the first and last occurrence of that number in the first list.
Input:
- the first line of the input contains two numbers N and M (\(1<=N,\ M <=20000\));
- the second line contains N non-decreasing integers — elements of the first list;
- the third line contains M of non-negative integers - elements of the second list.
All numbers in the lists are 32-bit signed integers.
Output: The program should output M lines. For each number from the second list, print the number of its first and last occurrence in the first list. The numbering starts from one. If the number is not included in the first list, you need to print a single number 0.
Examples
| # |
Input |
Output |
| 1 |
105
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
|
10 10
3 4
7 7
1 2
0
|