Ely found a magic number $$$K$$$, a magic basket with exactly one strawberry in it, and a magic coin. Everything seems to be magical.
Ely notices that when tossing the coin it falls heads up with probability $$$P$$$. Also, each time the coin falls heads up the number of strawberries in the basket get $$$K$$$ times bigger (i.e. if in the basket were $$$x$$$ strawberries, after the toss there will be $$$x \times K$$$). Ely decides to play the following game: she will toss the coin $$$N$$$ times; if it falls heads up she will just notice as the strawberries multiply $$$K$$$ times; if the coin falls tails up she will eat all the strawberries in the basket. After eating all the strawberries in the basket something magical happens: precisely a single new strawberry spawns inside of the basket.
Ely is now curious what is the expected number of strawberries she would eat after $$$N$$$ coin tosses. Help her find the answer.
The first line of the input will contain an integer $$$T$$$, the number of test cases ($$$1 \leq T \leq 10^5$$$).
Each of the next $$$T$$$ lines will contain three integers $$$N_i$$$ ($$$1 \leq N_i \leq 10^{18}$$$), $$$K_i$$$ ($$$0 \leq K_i \lt 998244353$$$), $$$P_i$$$ ($$$0 \leq P_i \lt 998244353$$$) the number of coin flips, the increasing factor for the strawberries and the probability that the coin lands head up, for the $$$i$$$th test case. The probability is a fraction $$$\frac{a}{b}$$$ given as $$$a \times b^{-1}$$$ (modulo 998244353), where $$$b^{-1}$$$ is the modular inverse of $$$b$$$ modulo 998244353.
The output file should contain $$$T$$$ lines, each with a single integer $$$A_i$$$, the answer for $$$i$$$th test case modulo 998244353.
4 1 2 499122177 3 2 499122177 10 2 499122177 1000000000000000000 100 16235235
499122177 748683267 748683281 565383148
Danny is an avid fan of Dungeon Crawlers and spends his time either playing them, or talking about them. Recently, he started wondering if it's possible for a computer to play one of his games, and he's been asking you to try it out for him.
The game is split into L levels, with N x M cells on every level. Every cell can have one of the following values:
- 0 - representing an empty cell;
- -1 - representing the exit to the next level;
- -9 - representing an obstacle you cannot pass through;
- K ($$$1 \leq K \leq 10^9$$$) - an integer representing the power level of an enemy.
In order to beat an enemy, your power needs to be greater than or equal to its power. Upon defeating it, you absorb its energy and your own power increases by a value equal to the power of the defeated enemy.
Given that you start with a power of 1 in the top left corner of the first level of the dungeon, what's the maximum power you can achieve? A path to the last level is always guaranteed.
The first line of input contains three integers: L N M, representing the number of levels, the number of rows and the number of columns ($$$1 \leq L * N * M \leq 10^6$$$). Then, there are L groups of N rows and M columns, describing the layout of the dungeon level.
On a single line, print an integer $$$P$$$ representing the maximum power you can get at the end of the dungeon.
1 5 5 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 5 0 0 0 0
4
2 5 5 0 0 -9 0 1 0 0 -9 -9 -9 0 0 1 0 0 0 0 -1 0 1 4 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 3 0 0 0 0 0 0 1 5 0 0 0 0
13
You decided to enter in the farming industry. So, you bought some farms to grow wheat on them. Because you are an entrepreneur, you want to be as profitable as possible.
The terrain of the farms is given as a matrix $$$A$$$ of size $$$N x M$$$, where on each cell of the matrix there is a non-negative quantity of wheat.
You administrate $$$Q$$$ farms of rectangular shape inside the matrix $$$A$$$.
The quantity of wheat of a farm is equal to the sum of values of the cells of $$$A$$$ that are inside the farm's rectangle.
For each farm you know the minimum quantity of wheat it needs in order to be profitable.
In the next $$$T$$$ days bad weather is announced. Thus, each day the quantity of wheat of some cells is decreasing.
Your task is to determine, for each farm, the total number of days it is profitable. If a farm is profitable an infinitely number of days, you should print $$$-1$$$.
A farm is profitable on day $$$i$$$ if, after all the updates until the day $$$i$$$ (including the updates on day $$$i$$$) caused by the bad weather, the quantity of wheat of the farm is greater or equal to the minimum quantity of wheat it needs in order to be profitable.
The first line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 500$$$), denoting the number of lines, respectively, the number of columns of the matrix $$$A$$$.
Then $$$N$$$ lines follow. Each line contains $$$M$$$ positive integers, denoting the values of the matrix $$$A$$$ ($$$0 \leq A_{i,j} \leq 10^9$$$).
The next line contains the integer $$$Q$$$ ($$$1 \leq Q \leq 50000$$$), denoting the number of farms you administrate.
Then $$$Q$$$ lines follow. Each line contains $$$5$$$ integers $$$X_1$$$, $$$Y_1$$$, $$$X_2$$$, $$$Y_2$$$, $$$MIN$$$ ($$$1 \leq X_1 \leq X_2 \leq N, 1 \leq Y_1 \leq Y_2 \leq M, 0 \leq MIN \leq 10^{18})$$$. The pair $$$(X_1, Y_1)$$$ denotes the upper-left corner of the farm, $$$(X_2, Y_2)$$$ denotes the lower-right corner of the farm, and the value $$$MIN$$$ denotes the minimum quantity of wheat the farm needs in order to be profitable.
The next line contains the integer $$$T$$$ ($$$1 \leq T \leq 50000$$$), denoting the number of days in which the value of some of the cells of the matrix $$$A$$$ is decreasing.
Then, the information for each day:
On the first line an integer $$$nr$$$, the number of updates of this day.
Then, $$$nr$$$ lines follow, each line contains $$$3$$$ integers, $$$x$$$, $$$y$$$ and $$$val$$$ ($$$1 \leq x \leq N, 1 \leq y \leq M, 1 \leq val \leq 10^9$$$), denoting that the value of the cell $$$(x, y)$$$ of the matrix $$$A$$$ is decreasing by $$$val$$$ (a pair $$$(x, y)$$$ can appear multiple times in the same day).
The total number of updates during the $$$T$$$ days is less or equal to $$$10^5$$$.
The value of a cell of matrix $$$A$$$ is always non-negative.
Note the unusual memory limit.
On a single line, print $$$Q$$$ integers, the answer for each farm in the order they appear in the input (the maximum number of days the farm is profitable, or $$$-1$$$ if it is profitable an infinitely number of days).
5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 2 1 2 3 10 2 2 5 6 15 3 4 4 5 1 1 2 5 4 13 5 1 5 6 6 4 2 5 6 1 5 4 1 3 1 3 1 2 2 1 2 3 1 1 3 3 1 2 4 6 1 1 1 1
0 3 -1 1 0
Farmer Dave has a big parcel where he harvests veggies. Unfortunately, there was a terrible storm which flooded some of the regions of his beloved parcel. You can visualize the parcel like a grid of $$$N$$$x$$$M$$$, where every region (cell) is having a non-negative quantity of water.
Farmer Dave happens to live in capitalism, where having a second job is strongly encouraged. He's not only a farmer, but also a part-time wizard! One magic trick with his wand allows him to slide all of the cells towards any cardinal point (North, South, East, West). By "sliding" is understood that all of the cells will shift towards the chosen direction. Any two adjacent cells holding the same quantity of water and moving towards the same cardinal point will merge into one having the same quantity incremented by one. Merging happens only if there is a strictly positive quantity of water in the cells to be merged and (it happens) continuously until no merge is possible. The order in which the cells get merged is opposite to the direction towards the cells are moving. For instance, if North is chosen, the first merged cells will be the northernmost ones and then further the southern cells.
If he plans to use the magic trick, the nature will punish Dave with one drop of water in the first available empty cell, North to South and then from West to East. If the nature can't apply the punishment (due to no empty cell available) then the nature will burn his magic wand so that he won't be able to do his magic anymore.
For example, for the following matrix the application of one magic trick towards North results in:
As another example, for the following matrix the application of one magic trick towards East results in:
Farmer Dave got at most $$$K$$$ magic tricks available and he believes that he will dry his parcel the fastest if he uses his super-skills to reach the highest possible quantity of water in a single cell. We believe this is stupid and that it does not make any sense, but let's prove that to him.
As Dave needs more data samples to understand that this approach is not a good heuristic for his parcel to get dry quicker, he will want you to compute the answer for more parcels.
he first line contains three integers: $$$N$$$ $$$(1 \leq N \leq 2500)$$$, $$$M$$$ $$$(1 \leq M \leq 2500)$$$ and $$$K$$$ $$$(1 \leq K * K \leq min(N, M))$$$. Moreover, $$$(1 \leq N * M \leq 2500)$$$.
The following $$$N$$$ lines will each contain $$$M$$$ integers, having the values in the interval [$$$0,10^6$$$].
The aforementioned format will apply to the subsequent parcels, so the contestants are advised to read until the end-of-file marker. It is guaranteed that the total number of cells (among all of the tests) is at most $$$2500$$$.
There will be as many lines as tests and each of them will contain an integer, the highest quantity of water which can end up in a cell using the optional given magic trick allowance.
4 4 1 1 2 3 4 1 2 3 4 1 1 3 5 1 1 4 0 4 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 2
Herbert is at school and tries to skip classes. The only problem is that he doesn't want to meet with his teachers when he leaves, so he needs to devise a tactic. Given the intervals of time in seconds when the corridors of the school are free, Herbert can choose any subinterval of those to leave.
Because he likes maths, he challenges himself to count in how many intervals of seconds can he escape the school without being caught. There is a problem: he doesn't have all the free intervals from the beginning of the day. He gets them either via his friends or his own observations. Given the list of free intervals that Herbert discovers, he sometimes stops and thinks in how many ways he could leave if he wanted to go home in a specific interval $$$[L, R]$$$. Help him do this task! He would like this answer to be given modulo $$$1000000007$$$ as he is not good at handling big numbers. Please note that the intervals of time are closed, that means if we have the free intervals $$$[a, b]$$$ and $$$[b + 1, c]$$$ they can be merged into a bigger interval $$$[a, c]$$$. It can happen the same if the intervals overlap or meet. Further, the intervals are not discovered in chronological order as his friends might not tell him instantly. Also, the length of an interval doesn't really matter, Herbert can move slowly or instantly as he is skilled!
The first line of input contains one integer $$$N$$$($$$1 \leq N \leq 10^6$$$): the total number of free intervals that will be discovered during the day plus the number of questions Herbert will ask.
The next $$$N$$$ lines of input will contain three integers $$$type$$$($$$1 \leq type \leq 2$$$), $$$l$$$ and $$$r$$$($$$1 \leq l \leq r \leq 10^{18}$$$): If $$$type$$$ is $$$1$$$ it means that the interval $$$[l, r]$$$ has been discovered as free. If $$$type$$$ is $$$2$$$ Herbert asks how many subintervals in $$$[l, r]$$$ are free given only the free intervals discovered above it.
For every query of the second type, print on a line an integer $$$x$$$, denoting the number of free subintervals in the given interval by Herbert modulo $$$1000000007$$$.
4 1 2 2 2 1 5 1 3 5 2 1 5
1 10
It's puzzle time! You're given as a present for your birthday a 3D, N-sided, coloured, puzzle and a picture of how it should look like solved.
Your puzzle is composed of a center piece, N edge pieces and N corner pieces. The centre piece has 2 visible sides top and bottom that determine the top color and bottom color of the puzzle respectively. Each edge piece has 3 visible sides: top, side, and bottom. Each corner piece has 4 visible sides: top, left, right, and bottom.
The $$$side_i$$$ of the puzzle ($$$1 \leq i \leq N - 1$$$) is made of ($$$corner_i, side_i, corner_{i + 1})$$$ in this exact order. The $$$side_n$$$ of the puzzle is made of ($$$corner_n, side_n, corner_1$$$) in this exact order.
The only move you have in your arsenal to solve the puzzle is $$$twist_i$$$ ($$$1 \leq i \leq N$$$), which rotates the $$$i$$$th side $$$180^\circ$$$. Performing this move would cause the following: both corner pieces would swap place, the top side and bottom side of both the corner pieces and the edge piece will be swapped, and the sides of both corner pieces will be swapped. That is, if you performed $$$twist_i$$$, where $$$side_i$$$ is ($$$c_{i1}, e_i, c_{i2}$$$), you get ($$$c_{i2}', e_i', c_{i1}'$$$), where: if $$$c_i = (t, l, r, b)$$$, $$$c_i' = (b, r, l, t)$$$ and if $$$e_i = (t, s, b)$$$, $$$e_i' = (b, s, t)$$$.
The solved puzzle:
- has $$$N + 2$$$ different colours on it: the top, the bottom, and each of the N sides.
- for each side face: the left corner's right, the side piece's side and the right corner's left have the same colour (each side has a solid color). The top sides of all 3 pieces have the colour of the top side of the puzzle. The bottom sides of all 3 pieces have the colour of the bottom side of the puzzle (i.e. all top sides form a solid colour and all bottom sides form a solid colour).
Given the initial state of all the pieces, your task is to say if there is a solution for the puzzle, and if so output a solution that leads you to the solved state.
The first line of the input contains $$$N$$$ ($$$4 \leq N \leq 100$$$), the number of sides of the puzzle.
The following line contains two integers col_top and col_bot, the colours of the top side of the puzzle and the colour of the bottom side of the puzzle respectively ($$$0 \leq col\_top,\ col\_bot \leq N + 1,\ col\_top \ne col\_bot$$$).
Each of the following $$$N$$$ lines contains a tuple ($$$ct_i, cl_i, cr_i, cb_i$$$) the top colour, the left colour, the right colour and the bottom colour for the $$$i$$$th corner ($$$0 \leq ct_i,\ cl_i,\ cr_i,\ cb_i \leq N + 1$$$).
Each of the followin $$$N$$$ lines contains a tuple ($$$et_i, es_i, eb_i$$$) the top colour, the side colour and the bottom colour of the $$$i$$$th edge ($$$0 \leq et_i,\ es_i,\ eb_i \leq N + 1$$$).
It is guaranteed that the set {$$$col\_bot,\ col\_top,\ es_1,\ es_2,\dots\ ,es_n$$$} = {$$$0,\ 1,\ 2,\dots\ ,\ n + 1$$$}. Obviously the order of the elements can differ.
If there is no solution you should output a single line containing the integer -1.
If there is a solution you should output two lines. The first line will contain an integer $$$k$$$, the number of moves in your solution. The following line will contain $$$k$$$ integers $$$t_1, t_2,\dots\ , t_k$$$, the twists performed on the puzzle to solve it ($$$1 \leq t_i \leq N$$$). If $$$t_i$$$ appears in your solution, it means that the $$$i$$$th move you made was a twist of the $$$t_i$$$th side of the puzzle.
Note that the MAXIMUM admitted $$$k$$$ is $$$10^5$$$.
4 0 5 5 4 3 0 0 1 2 5 0 2 3 5 5 1 4 0 0 1 5 0 2 5 5 3 0 0 4 5
5 1 2 3 2 1
For an input with $$$N = 4$$$ this is how the solved state would look like:
Being on a grind for the next hottest summer internship on the market, Sybren decided to solve the valid parentheses problem available on Leetcode in under 10 seconds - and he did!
However, he is serious about his pursuit. Therefore he decided to come up with another problem. Namely, you are given a tree with $$$N$$$ nodes. You must place '(' or ')' on every node. Can you do it in a way such that you maximize the number of pairs of nodes $$$(x, y)$$$ for which the simple path from $$$x$$$ to $$$y$$$ forms a valid parentheses match?
The first line of input contains an integer $$$N(1 \leq N \leq 10^5)$$$, denoting the number of nodes that the tree has. The next $$$N-1$$$ lines of input contain two integers $$$x$$$ and $$$y$$$, denoting that there is an edge between node $$$x$$$ and node $$$y$$$.
Print a string of $$$N$$$ parentheses which maximizes the number of valid paths $$$(x, y)$$$ which form a correct parentheses matching. In case there are multiple solutions, print the lexicographically minimal one. Parenthesis $$$p_i$$$ refers to the one which can be found in node number $$$i$$$.
3 1 2 1 3
())
You have a bag of $$$N$$$ cheques of values $$$A_1$$$, $$$A_2$$$, ..., $$$A_N$$$ dollars. You just met your old magician friend who has some special magical powers. By just waving his wand, two cheques from the bag are removed uniformly at random. In their place, a new cheque is added with a value equal to their sum. Moreover, you receive an amount of money equal to the value of the new cheque. Your friend is doing this until there is only one cheque left in the bag. To thank your friend, you give him the last cheque.
What is the expected value of the total amount of money you receive from the magic trick?
The first line of the input contains the integer $$$N$$$ ($$$2 \leq N \leq 500$$$), denoting the number of cheques.
The second line of the input contains $$$N$$$ integers $$$A_1$$$, $$$A_2$$$, ..., $$$A_N$$$ ($$$1 \leq A_i \leq 10^9$$$), denoting the value of each cheque.
On a single line, print the expected value of the total amount of money you receive thanks to your friend's magic trick. Your answer is considered correct if at least one of the absolute difference or the relative difference between your answer and judge's answer is less or equal than $$$10^{-6}$$$.
5 3 1 2 6 3
38.5000000000
River wants to cross a Bob. Oh no... I mean Bob wants to cross the AGM River (Amazing Great Massive River).
The AGM River is very wide so Bob cannot jump directly from the left side of the river to the right side. Fortunately for him, there are a lot of wooden logs floating on the river that he can jump on. These can be described as tuples $$$(x, y1, y2, c)$$$, signifying there is a log between $$$(x, y1)$$$ and $$$(x, y2)$$$ that takes $$$c$$$ energy for Bob to jump from (the logs shape vary and it's harder to keep your balance on some and easier on others).
Since the logs are so slippery, Bob can only jump horizontally and only between adjacent logs (i.e. he cannot jump over logs). Bob can freely move on a log. Formally, two logs $$$l_i = (x_i, y_{i_1}, y_{i_2}, c_i)$$$ and $$$l_j = (x_j, y_{j_1}, y_{j_2}, c_j)$$$ (where $$$x_i \lt x_j$$$) are adjacent if: $$$\exists\ d = y$$$ a horizontal line such as $$$y_{i_1} \lt y \lt y_{i_2}$$$ and $$$y_{j_1} \lt y \lt y_{j_2}$$$, and $$$\nexists\ l_k = (x_k, y_{k_1}, y_{k_2}, c_k)$$$ such as $$$x_i \lt x_k \lt x_j$$$ and $$$y_{k_1} \lt y \lt y_{k_2}$$$. If two such logs $$$l_i$$$ and $$$l_j$$$ exist, Bob will spend $$$c_i$$$ energy jumping from $$$l_i$$$ to $$$l_j$$$, and $$$c_j$$$ energy jumping from $$$l_j$$$ to $$$l_i$$$.
The first jump will start from the left side of the river (to the left of the leftmost log) to an adjacent log. This jump takes $$$0$$$ energy. The last jump will end on the right side of the river (to the right of the rightmost log) and will start from an adjacent log $$$l_r = (x_r, y_{r_1}, y_{r_2}, c_r)$$$. This takes $$$c_r$$$ energy.
Bob wants to conserve his energy for inventing new algorithms, so he asks you to find out what's the least energy he can spend in order to cross the river.
On the first line of the input you're given an integer $$$N$$$ ($$$1 \leq N \leq 250000$$$), the number of logs floating on the AGM River.
The following $$$N$$$ lines will each contain a tuple $$$(x_i, y_{i_1}, y_{i_2}, c_i)$$$, the description of the $$$i^{th}$$$ log ($$$1 \leq x_i \leq 10^9$$$, $$$1 \leq y_{i_1} \leq 10^9$$$, $$$1 \leq y_{i_2} \leq 10^9$$$, $$$y_{i_1} \lt y_{i_2}$$$, $$$1 \leq c_i \leq 10^9$$$).
There are no overlapping logs. That is, $$$\forall$$$ $$$l_i=(x_i, y_{i_1}, y_{i_2}, c_i)$$$ and $$$l_j=(x_j, y_{j_1}, y_{j_2}, c_i)$$$, if $$$x_i = x_j$$$ then $$$y_{i_2} \leq y_{j_1}$$$ or $$$y_{j_2} \leq y_{i1}$$$.
For each log $$$i$$$, the interval $$$(y_{i_1}, y_{i_2})$$$ is open, i.e. the ends $$$y_{i_1}$$$ and $$$y_{i_2}$$$ are not considered part of the interval.
The output file should contain a single integer, the answer to Bob's query.
8 1 1 4 10 4 2 5 10 2 3 5 1 3 2 4 1 2 1 3 1 5 1 3 1 6 1 2 10 6 2 3 10
4
Explanation for the above example:
Some countries are more likely to face disasters than others - be it economic or natural. This country is very prone to natural disasters, so it has set in place an elaborate system which is meant to minimize the amount of casualties. There are $$$N$$$ houses placed in the shape of a tree, with $$$N-1$$$ roads. Initially, none of these roads are blocked. The first house also works as a shelter in case of natural disasters.
Two different kind of updates can be made to this system, namely:
- 1 x y - house x will now have y people;
- 2 x - the first road on the path from home x to the shelter is now switching its state, i.e. if it was previously blocked, it becomes unblocked, and vice versa.
To make sure that the system works as intended, its developers want to check the total number of people that can get from all houses to the shelter after every update. However, they are not the kind of competitive programmers that would implement Treaps at A.G.M., so they require your help.
The first line of input contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$), denoting the number of houses and the number of updates made to the system.
Then $$$N-1$$$ lines will follow. Each line will contain two integers $$$x$$$, $$$y$$$, meaning that there is a road between house $$$x$$$ and house $$$y$$$.
The next line will contain $$$N$$$ integers $$$x_i$$$ ($$$0 \leq x_i \leq 10^9$$$) representing the amount of citizens currently living in house $$$i$$$.
Lastly, $$$Q$$$ lines will follow. Each line will represent an update. According to the update type, this might either be:
- $$$1$$$ $$$x$$$ $$$y$$$, meaning that house $$$x$$$ will now host $$$y$$$ ($$$0 \leq y \leq 10^9$$$) people in total.
- $$$2$$$ $$$x$$$, meaning that the first road on the path from home x to the shelter is now switching its state.
The output shall contain $$$Q$$$ lines. On every line, print an integer $$$x_i$$$, denoting the number of people that can reach the shelter after update $$$q_i$$$ has been executed.
4 6 1 2 2 3 3 4 1 1 1 1 1 2 2 2 4 2 2 1 4 10 2 4 2 2
5 4 1 1 1 14
9 15 1 2 1 3 3 4 3 5 4 6 3 7 7 8 7 9 5 65 70 8 1 500 18 21 180 2 7 1 3 200 2 3 1 6 300 2 6 1 9 100 2 7 2 6 1 4 20 2 2 2 3 1 2 9 1 7 0 2 3 2 2
649 779 70 70 70 70 70 70 70 5 665 665 647 5 14
You are given an array $$$A$$$ of $$$N$$$ integers $$$A_1$$$, $$$A_2$$$, …, $$$A_N$$$, and an array $$$B$$$ of $$$K$$$ integers $$$B_1$$$, $$$B_2$$$, …, $$$B_K$$$.
You are asked to split the array $$$A$$$ into $$$K$$$ non-empty subarrays (consecutive positions within the array). The cost of a split is equal to $$$\sum_{i=1}^{K} max_i^{B_i} - min_i^{B_i}$$$, where $$$max_i$$$ denotes the maximum in the $$$i^{\text{th}}$$$ subarray, and $$$min_i$$$ denotes the minimum in the $$$i^{\text{th}}$$$ subarray.
Calculate the maximum cost you can obtain by splitting the array $$$A$$$ into $$$K$$$ non-empty subarrays.
The first line contains two integers: $$$N$$$ $$$(1 \leq N \leq 5000)$$$ and $$$K$$$ $$$(1 \leq K \leq N)$$$.
The second line contains $$$N$$$ integers: $$$A_1$$$, $$$A_2$$$, …, $$$A_N$$$ $$$(1 \leq A_i \leq 10^5)$$$.
The third line contains $$$K$$$ integers: $$$B_1$$$, $$$B_2$$$, …, $$$B_K$$$ $$$(1 \leq B_i \leq 3)$$$.
On a single line, print the maximum cost you can obtain by splitting the array $$$A$$$ into $$$K$$$ non-empty subarrays.
10 3 2 6 10 1 5 9 7 2 1 8 3 1 2
1079
You decided to have your 'La casa de papel' moment - and good for you. The main difference is that, instead of stealing gold, you decided to steal... uranium.
The road from the starting point $$$S$$$ to the destination $$$D$$$ is quite complicated. Luckily, you have a map! On this map, you have $$$N$$$ ($$$1 \leq N \leq 10^5$$$) locations that you can get to, and $$$M$$$ ($$$1 \leq M \leq 2 \times 10^5$$$) paths connecting two locations together. Each of these paths has a length of $$$l_i$$$ ($$$1 \leq l_i \leq 10^9$$$) meters. To make things more exciting, the police knows about your plan and are waiting for you in $$$K$$$ ($$$1 \leq K \leq N$$$) different locations that you know of. They are equipped with uranium detectors.
Keep in mind that the more uranium you have, the farther away it can be detected from. In other words, if you decide to steal $$$x$$$ units of uranium, said quantity will be detectable by any cop who is at most $$$x$$$ units of distance away from you.
Having all of this information, you want to know the maximum quantity of uranium that you can steal without being detected by the police. Furthermore, the adrenaline rush of stealing turned you addicted. Therefore, you do not do steal uranium just once - you do it $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$) times, each time with a different starting and ending point.
The first line of input contains two integers $$$N$$$($$$1 \leq N \leq 10^5$$$), $$$M$$$($$$1\leq M \leq 2 \times 10^5$$$): the number of different locations, the number of roads between these locations.
The next $$$M$$$ lines of input will contain three integers $$$x$$$, $$$y$$$ and $$$l_i(1 \leq l \leq 10^9)$$$ , signifying that there is a road from spot $$$x$$$ to spot $$$y$$$ with a length of $$$l_i$$$ meters. Note that there are no roads going from a city to itself, but there may be multiple roads connecting the same two cities.
The next line of input contains an integer $$$K$$$($$$1 \leq K \leq 10^5$$$): the number of police locations.
The following line will contain $$$K$$$ integers $$$P_i$$$, signifying that spot $$$P_i$$$ is being camped by cops.
The next line of input contains an integer $$$Q$$$($$$1 \leq Q \leq 10^5$$$): the number of queries.
Lastly, there will be $$$Q$$$ lines, each of them representing a query. There will be two integers $$$x$$$, $$$y$$$, signifying that you start your stealing adventure from spot $$$x$$$ and that your destination is spot $$$y$$$.
For every query, print on a line an integer $$$x$$$, denoting the maximum amount of uranium that you can 'borrow' without being caught.
5 6 1 2 1 2 3 3 3 4 3 2 4 4 1 5 1 4 5 1 1 2 3 1 3 5 3 4 3
0 1 2
9 10 1 2 1 2 3 4 2 4 2 4 5 5 5 9 10 5 6 10 6 7 2 6 9 5 9 8 8 8 7 3 2 4 9 5 1 3 1 6 5 7 6 9 7 8
1 0 4 0 6