Next Greater Element I

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Given two arrays nums1 and nums2 whose elements are pairwise distinct, and every element of nums1 occurs in nums2. For each value $x$ in nums1, locate $x$ in nums2 and find the first element to its right whose value is greater than $x$. If none exists, the answer is $-1$.

Input

The first line contains $m$ and $n$, the lengths of nums1 and nums2. The second line contains nums1. The third line contains nums2.

Output

Print $m$ integers in nums1 order, each being the corresponding next greater element in nums2, or $-1$.

Subtasks

• Subtask 1 (30 points): Original constraints, and nums2 is strictly increasing.
• Subtask 2 (70 points): $1\le m\le n\le1000$, $0\le nums1_i,nums2_i\le10^4$; mỗi mảng không có phần tử lặp và nums1 là tập con của nums2.

Examples

Input

3 4
4 1 2
1 3 4 2

Output

-1 3 -1

Explanation

Here nums1 = [4,1,2] and nums2 = [1,3,4,2].

• Value $4$ is at the third position of nums2. Only $2<4$ lies to its right, so there is no next greater element: the answer is $-1$.
• Value $1$ is at the first position of nums2. The immediately following value is $3>1$, so the answer is $3$.
• Value $2$ is at the last position of nums2, so nothing lies to its right: the answer is $-1$.

In nums1 order, the program prints -1 3 -1.