Khayyam Finals 2025

Electi Courses - KhIMIO

2 сМаҳдудияти вақт

512 МБМаҳдудияти ҳофиза

Тавсифи масъала

ElectiCode prepared $M$ special courses for his students. There are $N$ students in total, and the rating of the $i$ -th student is denoted by $r_i$ .

Farhod is going to teach exactly one student in each course. The process repeats exactly $M$ times:

He chooses the student with the lowest current rating; if there are multiple such students, he selects the one with the smallest index.

Ҳал кардан мехоҳӣ?

Ворид шав, кодро ҳамин ҷо навис ва натиҷаро дарҳол бин.

Ворид шудан

Намуд

He teaches this student special techniques, increasing their rating by

S

Student $1$ became curious and started imagining $Q$ different scenarios.
In the $i$ -th scenario, he wonders what his final rating would be if his initial rating was $q_i$ .

Input Format

The first line contains one integer $T \ (1 \leq T \leq 10^3)$ $T (1 \leq T \leq 1 0^{3})$ , the number of tests.
- Then, for each test:
  - The first line contains four space-separated integers $N, M, Q, S$ $(1 \leq N, M, Q \leq 2 \cdot 10^5, 1 \leq S \leq 10^9)$ .
  - The second line consists of $N$ space-separated integers $r_1, r_2, \ldots, r_N$ .
  - The third line consists of $Q$ space-separated integers $q_1, q_2, \ldots, q_Q$ .
- The total sum of $N$ in all tests doesn't exceed $2 \cdot 10^5$ .
- The total sum of $M$ in all tests doesn't exceed $2 \cdot 10^5$ .
- The total sum of $Q$ in all tests doesn't exceed $2 \cdot 10^5$ .

Output Format

For each test, print one line consisting of $Q$ space-separated integers.

Scoring

Let $S_N$ be the total sum of $N$ in all tests.

Subtasks	Additional restrictions	Points	Required Subtasks
0	Sample	0	-
1	$S_N \leq 200, \ Q = 1$	10	-
2	$S_N \leq 2 \ 000, \ Q = 1$	12	1
3	$Q = 1$	13	1, 2
4	$N \leq 2, \ r_i = 0$	13	-
5	$N \leq 200, \ r_i = 0$	15	4
6	$N \leq 2 \ 000, \ r_i = 0$	17	4, 5
7	-	20	0, 1, 2, 3, 4, 5, 6

Мисолҳо

Мисол 1

Вуруд

2 2 5 4 3 0 0 1 2 3 4 4 10 4 1 1 2 3 4 1 3 5 7

Баромад

7 8 9 10 5 6 6 7

(0 \leq r_i \leq 10^9)

(0 \leq q_i \leq 10^{18})

(0 \leq q_{i} \leq 1 0^{18})