Есептің шарты

Жазудан шаршадым, енді жазғым келмейді.

«Мұны „шаршау“ деп атайды».

Ұзындығы $n$ болатын $a_1,a_2\ldots a_n$ тізбегі берілген, әрбір $i$ орнының өзгерту құны $c_i$ болады. Белгілі бір орын үшін $c_i$ құнын төлеп, $a_i$ мәнін кез келген мәнге өзгерте аласыз. Тізбектің әрбір префикстік қосындысы $r$-ге бөлінбейтіндей етіп жалпы құнды барынша азайтқыңыз келеді.

Формальды түрде, $s_i=\sum_{j=1}^{i}a_j$ болсын. Өзгертілген тізбек үшін барлық $1 \le i \le n$ мәндерінде $s_i \bmod r \ne 0$ орындалатынына көз жеткізуіңіз керек.

Кіріс деректер

Бірінші жолда тест жиынтықтарының саны $T$ ($1 \le T \le 10^5$) берілген.

Әрбір тест жиынтығы үшін бірінші жолда екі оң бүтін сан $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$) берілген.

Келесі жолда тізбекті білдіретін $n$ теріс емес бүтін сан $a_i$ ($0 \le a_i < r$) берілген.

Келесі жолда өзгерту құндарын білдіретін $n$ теріс емес бүтін сан $c_i$ ($0 \le c_i \le 10^9$) берілген.

Барлық $n$ сандарының қосындысы $5\cdot 10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін жеке жолға ең аз құнды білдіретін бір бүтін санды шығарыңыз.

Мысалдар

Кіріс 1

5
3 3
2 1 2
3 2 1
4 2
0 1 0 0
2 1 3 1
5 3
2 1 1 0 2
3 2 4 1 5
6 3
0 2 1 1 2 0
6 2 4 5 5 1
7 4
1 2 3 0 1 2 3
3 4 1 7 5 2 3

Шығыс 1

2
3
2
10
2