B - Library Book Lending Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は大学の図書館でアルバイトをしています。この図書館では、学生の学習レベルに応じて借りられる本が制限されています。

図書館には N 人の学生が登録されており、それぞれ 1 から N までの番号が付けられています。学生 i の学習レベルは整数 S_i です。

図書館には M 冊の本があり、それぞれ 1 から M までの番号が付けられています。本 j を借りるために必要な最低学習レベルは整数 T_j です。

学生 i が本 j を借りることができるのは、S_i \geq T_j を満たすときに限ります。

なお、同じ本を複数の学生がそれぞれ借りることができます。すなわち、ある学生が借りられる本の冊数は、他の学生の貸出状況に影響されません。

N 人の学生それぞれについて、その学生が借りることのできる本の冊数を求めてください。すなわち、各 i (1 \leq i \leq N) について、S_i \geq T_j を満たす本 j (1 \leq j \leq M) の個数 C_i を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_M
  • 1 行目には、学生の人数 N と本の冊数 M が、スペース区切りで与えられる。
  • 2 行目には、各学生の学習レベル S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • 3 行目には、各本を借りるために必要な最低学習レベル T_1, T_2, \ldots, T_M が、スペース区切りで与えられる。

出力

C_1
C_2
\vdots
C_N

N 行出力せよ。i 行目 (1 \leq i \leq N) には、学生 i が借りることができる本の冊数 C_i を出力せよ。

入力例 1

3 4
2 1 3
1 2 3 2

出力例 1

3
1
4

入力例 2

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

出力例 2

2
3
4
5
6

入力例 3

8 10
100 500 200 1000 300 50 750 400
150 300 500 100 250 600 800 450 200 350

出力例 3

1
8
3
10
5
0
9
6

Score : 333 pts

Problem Statement

Takahashi works part-time at a university library. At this library, the books a student can borrow are restricted based on their study level.

There are N students registered at the library, numbered from 1 to N. The study level of student i is an integer S_i.

The library has M books, numbered from 1 to M. The minimum study level required to borrow book j is an integer T_j.

Student i can borrow book j if and only if S_i \geq T_j.

Note that the same book can be borrowed by multiple students independently. That is, the number of books a student can borrow is not affected by the borrowing status of other students.

For each of the N students, determine the number of books that student can borrow. Specifically, for each i (1 \leq i \leq N), find the count C_i of books j (1 \leq j \leq M) satisfying S_i \geq T_j.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
  • All inputs are integers

Input

N M
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_M
  • The first line contains the number of students N and the number of books M, separated by a space.
  • The second line contains the study levels of each student S_1, S_2, \ldots, S_N, separated by spaces.
  • The third line contains the minimum study levels required to borrow each book T_1, T_2, \ldots, T_M, separated by spaces.

Output

C_1
C_2
\vdots
C_N

Output N lines. The i-th line (1 \leq i \leq N) should contain C_i, the number of books that student i can borrow.

Sample Input 1

3 4
2 1 3
1 2 3 2

Sample Output 1

3
1
4

Sample Input 2

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

Sample Output 2

2
3
4
5
6

Sample Input 3

8 10
100 500 200 1000 300 50 750 400
150 300 500 100 250 600 800 450 200 350

Sample Output 3

1
8
3
10
5
0
9
6