Truy vấn số phần tử không lớn hơn (Queries about less or equal elements)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho hai dãy số nguyên:

và

Với mỗi phần tử $b_j$, hãy tính số phần tử của dãy $a$ không lớn hơn $b_j$, tức là số chỉ số $i$ thỏa:

Input

Dòng đầu gồm hai số nguyên $n$ và $m$.

Dòng thứ hai gồm $n$ số nguyên của dãy $a$.

Dòng thứ ba gồm $m$ số nguyên của dãy $b$.

Output

In $m$ số nguyên trên một dòng. Số thứ $j$ là số phần tử $a_i\le b_j$.

Subtask

• Subtask 1 — 20%: $1\le n,m\le100$.
• Subtask 2 — 30%: $1\le n,m\le5000$.
• Subtask 3 — 50%: $1\le n,m\le2\cdot10^5$, $-10^9\le a_i,b_j\le10^9$.

Ví dụ

Input

5 4
1 3 5 7 9
6 4 2 8

Output

3 2 1 4

Giải thích

Dãy $a$ là $[1,3,5,7,9]$.

• Với $b_1=6$, có $3$ phần tử không lớn hơn $6$: $1,3,5$.
• Với $b_2=4$, có $2$ phần tử: $1,3$.
• Với $b_3=2$, có $1$ phần tử: $1$.
• Với $b_4=8$, có $4$ phần tử: $1,3,5,7$.

Vì vậy kết quả là 3 2 1 4.