A - Announcement of Winning Numbers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は商店街の福引イベントの係員をしています。このイベントには N 人の来場者が順番に福引を引きます。

各来場者には2種類の番号があります。i 番目 (1 \leq i \leq N) に福引を引いた来場者には、福引を引いた順に 整理番号 i が割り当てられます。また、各来場者は受付時に参加券を受け取っており、i 番目に福引を引いた来場者の 参加券の番号 は A_i です。なお、異なる来場者の参加券の番号が同じである場合もあります。

高橋君の任務は、整理番号が K の倍数（すなわち K, 2K, 3K, \ldots）である来場者全員に景品を渡すことです。K \leq N であるため、景品を受け取る来場者は必ず 1 人以上存在します。

景品を受け取る来場者の参加券の番号を、整理番号が小さい順にすべて出力してください。参加券の番号が同じ来場者が複数いる場合は、その番号を重複を除かずそのまま出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N K
A_1 A_2 \ldots A_N
  • 1 行目には、来場者の人数を表す整数 N と、景品を渡す基準となる整数 K が、スペース区切りで与えられる。整理番号が K の倍数である来場者に景品が渡される。
  • 2 行目には、i 番目に福引を引いた来場者の参加券の番号を表す整数 A_i が N 個、スペース区切りで与えられる。

出力

景品を受け取る来場者の参加券の番号を、整理番号が小さい順にスペース区切りで 1 行で出力し、末尾に改行を出力してください。

入力例 1

6 2
10 20 30 40 50 60

出力例 1

20 40 60

入力例 2

10 3
100 200 300 400 500 600 700 800 900 1000

出力例 2

300 600 900

入力例 3

15 4
1000000000 999999999 123456789 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998 100000007 314159265

出力例 3

987654321 444444444 888888888

Score : 200 pts

Problem Statement

Takahashi is a staff member at a shopping district's lottery event. In this event, N visitors draw the lottery one by one in order.

Each visitor has two types of numbers. The i-th (1 \leq i \leq N) visitor to draw the lottery is assigned a sequence number i in the order they drew. Additionally, each visitor received a participation ticket at registration, and the participation ticket number of the i-th visitor to draw the lottery is A_i. Note that different visitors may have the same participation ticket number.

Takahashi's task is to give a prize to every visitor whose sequence number is a multiple of K (i.e., K, 2K, 3K, \ldots). Since K \leq N, there is at least one visitor who receives a prize.

Output all participation ticket numbers of the visitors who receive prizes, in ascending order of their sequence numbers. If multiple visitors have the same participation ticket number, output that number as-is without removing duplicates.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of visitors and an integer K representing the criterion for giving prizes, separated by a space. Prizes are given to visitors whose sequence numbers are multiples of K.
  • The second line contains N integers A_i, each representing the participation ticket number of the i-th visitor to draw the lottery, separated by spaces.

Output

Output the participation ticket numbers of the visitors who receive prizes in ascending order of their sequence numbers, separated by spaces on a single line, followed by a newline.

Sample Input 1

6 2
10 20 30 40 50 60

Sample Output 1

20 40 60

Sample Input 2

10 3
100 200 300 400 500 600 700 800 900 1000

Sample Output 2

300 600 900

Sample Input 3

15 4
1000000000 999999999 123456789 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998 100000007 314159265

Sample Output 3

987654321 444444444 888888888