## The Potion of Great Power SOLUTION Codeforces

Sometime in the distant past, in the Land of the Shamans, everybody lived on the Sky-High Beanstalk. Every shaman had an exceptional distinguishing number I somewhere in the range of 0 and N−1, and a height esteem Hi, speaking to how high he lived over the ground level. The separation between two heights is the total estimation of their distinction.

All shamans lived respectively in harmony, until one of them took the recipe of the world-well known Potion of Great Power. To cover his/her tracks, the Thief has put a Curse on the land: most occupants could no longer confide in one another… In spite of the troublesome conditions, the Order of Good Investigators have picked up the accompanying data about the Curse: At the point when the Curse first produces results, everybody quits confiding in one another. The Curse is insecure: toward the finish of every day (precisely at 12 PM), one sets of shamans will begin or quit confiding in one another. Tragically, every shaman will just ever trust all things considered D others at some random time.

They have likewise recreated a log of who confided in whom: for every night they realize which pair of shamans began/quit confiding in one another.

They accept the Thief has murmured the recipe to an Evil Shaman. To stay away from identification, them two visited the home of one of their (separate) confided in companions. During the visit, the Thief murmured the equation to the Evil Shaman through the window. (Note: this believed companion didn’t need to be home at that point. Indeed, it’s even conceivable that they visited each other’s homes – shamans are bizarre.)

Luckily, murmurs just travel short separations, so the Order realizes the two believed companions visited (by the Thief and the Evil Shaman) should live exceptionally near one another.

They request that you help with their examination. They might want to test their doubts: imagine a scenario in which the Thief was x, the Evil Shaman was y, and the equation was murmured on day v. What is the littlest separation the murmured equation needed to travel? That is, what is the base separation between the lofts of certain shamans x′ and y′ (for example min(|Hx′−Hy′|)), with the end goal that x′ was a confided in companion of x and y′ was a confided in companion of y on day v?

They will impart all their data to you, at that point ask you various inquiries. You have to respond to each address quickly, before getting the following one.

Communication

The communication will start with a line containing N, D, U and Q (2≤N≤100000, 1≤D≤500, 0≤U≤200000, 1≤Q≤50000) – the quantity of shamans, the greatest number of confided in companions a shaman can have at some random point, the quantity of days, and the quantity of inquiries.

On the following line N space isolated numbers will follow, the ith (1≤i≤N) of which being Hi−1 (0≤Hi−1≤109), the elevation of shaman i−1.

On the following U lines there will be two numbers each, on the ith Ai and Bi (0≤Ai,Bi<N and Ai≠Bi), which speaks to a couple of shamans who began or quit confiding in one another toward the finish of day i−1. That is, if Ai and Bi confided in one another on day I, they didn’t confide in one another on day i+1, or the other way around. Peruse these numbers.

The interactor now will ask you Q inquiry, so the accompanying association ought to happen Q times:

Peruse 3 whole numbers depicting the current inquiry: x,y and v (x≠y, 0≤x,y<N and 0≤v≤U), where x is the speculated Thief, y is the presumed Evil Shaman, and v is the speculated day..

At that point print the response to this inquiry on a solitary line, for example you should print the base separation the murmured equation needed to go from some confided in companion x′ of x to a confided in companion y′ of y.

On the off chance that somebody confided in both x and y (for example x′=y′), you should print 0. On the off chance that x or y had no confided in companions, print 109. Subsequent to printing each line remember to yield end of line and flush the yield. Else, you will get Idleness limit surpassed. To do this, utilization: fflush(stdout) or cout.flush() in C++; System.out.flush() in Java; flush(output) in Pascal; stdout.flush() in Python; see documentation for different dialects.