Көңіл аударыңыз: жадтың ерекше шектеуі бар!

Мансур, Вансур және Уансур бір үйде тұрады. Мансурдың ұзындығы \(n\) болатын оң сандардан тұратын \(a_1,\ldots,a_n\) массиві бар. Әрбір санды ол мұқият өсірген: суарып және күтіп баққан.

Мансур ЧРК-ға кеткен кезде, Вансур мен Уансур массивпен ойнауды шешті, дегенмен Мансур оларға мұны жасауға тыйым салған болатын.

Әрбір \(q\) раундында Вансур бір санды \(d\) ойлап тауып, оны Уансуру хабарлайды. Өз кезегінде Уансур \(d\)-ге бөлінетін әрбір санды \(d\) есе азайтады. Осыдан кейін Уансур массивтегі сандардың қосындысын Вансуруға хабарлауы керек.

Мысалы, егер массив \(a=[1,2,6,9,12]\) және \(d = 6\) болса, онда модификациядан кейін массив осындай болады \([1,2,1,9,2]\).

Кейде олар рөлдерін ауыстырады. Бұл ойынның мақсаты: мүмкіндігінше тез жауап беру, осылайша Вансур мен Уансур өз қабілеттерін жаттықтырады. Сіз де жаттығып көріңіз!

Енгізу

Бірінші жолда екі сан бар: \(n\) және \(q\) (\(1 \le n, q, \le 10^6\)) – Мансурдың массивінің ұзындығы және ойынның раунд саны.

Келесі жолда \(n\) сан бар: \(a_1,\ldots,a_n\) (\(1 \le a_i \le 10^6\)) – Мансурдың массиві.

Келесі \(q\) жолда бір сан бар: \(d\) (\(1 \le d \le 10^6\)) – Вансур немесе Уансурдың сұрақтары.

Шығару

Әрбір сұрақтан кейін операцияны қолданғаннан кейін массив элементтерінің қосындысын шығарыңыз.

Мысалдар

Енгізу 1

10 3
1 2 3 4 5 6 7 8 9 10
3
3
5

Жауап 1

43
41
29

Енгізу 2

3 3
8 6 27
9
4
6

Жауап 2

17
11
6