바이토치아에 높은 탑이 세워졌습니다. 탑의 입구는 n개의 계단으로 이루어져 있으며, 각 계단은 특정 높이를 가지고 있습니다.
m명의 바이토치아 주민들이 이 탑을 방문하고자 합니다. 각 사람은 계단을 오르는 데 도움이 되는 특정 키를 가지고 있습니다. 바이토치아 주민이 특정 계단에 올라가기 위해서는 그 계단의 높이보다 키가 더 커야 합니다. 만약 어떤 계단을 올라갈 수 없다면, 그 주민은 해당 위치에서 멈추게 됩니다 - 더 높이 올라갈 수 없습니다.
각 계단의 높이와 방문객들의 키를 알고 있을 때, 각 바이토치아 주민이 어디에서 멈추게 될지 알고 싶습니다.
입력
첫 번째 줄에는 두 개의 정수 n, m (1 ≤ n, m ≤ 500,000)이 주어지며, 각각 탑으로 이어지는 계단의 수와 탑을 방문하고자 하는 주민의 수를 나타냅니다. 다음 줄에는 n개의 정수 a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 10⁹)가 주어지며, aᵢ는 i번째 계단의 높이를 나타냅니다. 첫 번째 계단은 탑의 가장 아래에 있으며, 각 계단은 이전 계단보다 위에 있습니다. 다음 줄에는 m개의 정수 b₁, b₂, ..., bₘ (1 ≤ bᵢ ≤ 10⁹)가 주어지며, bᵢ는 i번째 주민의 키를 나타냅니다.
출력
첫 번째이자 유일한 출력 줄에는 m개의 정수 w₁, w₂, ..., wₘ이 있어야 하며, wᵢ는 i번째 바이토치아 주민이 올라갈 수 있는 가장 높은 계단의 번호를 나타냅니다.
hanzch 1년 전
탑
문제
바이토치아에 높은 탑이 세워졌습니다. 탑의 입구는 n개의 계단으로 이루어져 있으며, 각 계단은 특정 높이를 가지고 있습니다. m명의 바이토치아 주민들이 이 탑을 방문하고자 합니다. 각 사람은 계단을 오르는 데 도움이 되는 특정 키를 가지고 있습니다. 바이토치아 주민이 특정 계단에 올라가기 위해서는 그 계단의 높이보다 키가 더 커야 합니다. 만약 어떤 계단을 올라갈 수 없다면, 그 주민은 해당 위치에서 멈추게 됩니다 - 더 높이 올라갈 수 없습니다. 각 계단의 높이와 방문객들의 키를 알고 있을 때, 각 바이토치아 주민이 어디에서 멈추게 될지 알고 싶습니다.
입력
첫 번째 줄에는 두 개의 정수 n, m (1 ≤ n, m ≤ 500,000)이 주어지며, 각각 탑으로 이어지는 계단의 수와 탑을 방문하고자 하는 주민의 수를 나타냅니다. 다음 줄에는 n개의 정수 a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 10⁹)가 주어지며, aᵢ는 i번째 계단의 높이를 나타냅니다. 첫 번째 계단은 탑의 가장 아래에 있으며, 각 계단은 이전 계단보다 위에 있습니다. 다음 줄에는 m개의 정수 b₁, b₂, ..., bₘ (1 ≤ bᵢ ≤ 10⁹)가 주어지며, bᵢ는 i번째 주민의 키를 나타냅니다.
출력
첫 번째이자 유일한 출력 줄에는 m개의 정수 w₁, w₂, ..., wₘ이 있어야 하며, wᵢ는 i번째 바이토치아 주민이 올라갈 수 있는 가장 높은 계단의 번호를 나타냅니다.
예제 입력 1
예제 출력 1