legendary-graph-icpc-6

One night, while sitting around a campfire, Rory Mercury tells a strange story from a long time ago…

Legend tells of a legendary graph with N vertices numbered from 1 to N and no edges. Each of its vertices had an interval [Pi, Qi] associated with. The intervals might have represented something meaningful long ago, but the meaning has been long forgotten. The graph existed for a total of T years, with a major event occurring at the end of every year of its existence. At the end of the i^th year, the graph either grew an edge from Ui to Vi or asked itself a question in an attempt to gain some self-identity and graduate from being just another abstract mathematical object. The questions it asks itself are in the form "What is the sum of lengths of the intersections between an interval [Xi, Yi] and every vertex in my connected component containing the vertex Zi?" Recall that the intersection of two intervals is the longest interval that is contained within both intervals. If the intervals are disjoint then the length of the intersection is zero, otherwise the length of an interval [L, R] is equal to R - L + 1 (we use "number of integers" as the length of an interval instead of the standard definition).

Rory then described each of the T events in great detail. There are so many events that you almost fell asleep. To stay awake, you decide to reproduce the answers to the questions of the graph.

Input Format: 
The first line of input will contain two integers N and T. 
The second line of input will contain five integers A, B, C, D, and E, the initial state of a pseudorandom number generator. 
The function randInt will return a pseudorandom number, modifying the state of the generator in the process. Watch out for integer overflow when you implement it.

function randInt(MIN, MAX):
    F = (A * C + B * D + E) modulo 1,000,000,007
    A = B
    B = F
    return ( F modulo (MAX - MIN + 1) ) + MIN

The intervals of the vertices of the graph are given by this pseudocode: 
for i from 1 to N, inclusive:
    P = randInt(1, 1,000,000)
    Q = randInt(P, 1,000,000)
    the interval of vertex i is [P, Q]

After the intervals of the vertices of the graph are determined, the events are described by this pseudocode: 
for i from 1 to T, inclusive:
    if randInt(1, 2) is equal to 1:
        U = randInt(1, N)
        V = randInt(1, N)
        event i is that the graph grows an edge from U to V
    else:
        X = randInt(1, 1,000,000)
        Y = randInt(X, 1,000,000)
        Z = randInt(1, N)
        event i is that the graph asks the question with the interval [X, Y] and vertex Z
Note: It is important that you execute the code sequentially, generating the queries after the intervals, because randInt will modify the state of the pseudorandom generator. It follows that you should not call randInt outside of the generator code before you finish generating all the input.

Output Format: 
Let answer be the sum of i * vali over all i from 1 to T, inclusive, where vali is the answer to the question the graph asked itself, if it asked one, otherwise it is 0. Output answer modulo 10^9+7.

Constraints: 
1 ≤ N ≤ 10^6 
1 ≤ T ≤ 3 × 10^6 
1 ≤ Pi ≤ Qi ≤ 10^6 
1 ≤ Xi ≤ Yi ≤ 10^6 
1 ≤ Ui, Vi, Zi ≤ N 
0 ≤ A, B, C, D, E < 10^9+7 

SAMPLE INPUT
20 25
1 2 3 4 5

SAMPLE OUTPUT
73387766

Explanation

Here are the correct values of the generator and the answers to the questions. Note that the sample input may not be very useful to debug your solution on due to the large and random values.

P1 = 17, Q1 = 92 
P2 = 354, Q2 = 1996 
P3 = 7633, Q3 = 43092 
P4 = 164738, Q4 = 930068 
P5 = 555537, Q5 = 628508 
P6 = 739170, Q6 = 955122 
P7 = 261898, Q7 = 287841 
P8 = 109133, Q8 = 127921 
P9 = 43772, Q9 = 163527 
P10 = 980757, Q10 = 981199 
P11 = 182599, Q11 = 528249 
P12 = 190293, Q12 = 780808 
P13 = 543095, Q13 = 776958 
P14 = 235311, Q14 = 551568 
P15 = 288943, Q15 = 619689 
P16 = 238868, Q16 = 562185 
P17 = 654537, Q17 = 978281 
P18 = 250007, Q18 = 966593 
P19 = 609305, Q19 = 849427 
P20 = 154568, Q20 = 715924 

event 1 is a grow event: U1 = 8, V1 = 14 
event 2 is a question event: X2 = 861828, Y2 = 952669, Z2 = 4 
event 3 is a grow event: U3 = 5, V3 = 2 
event 4 is a grow event: U4 = 19, V4 = 9 
event 5 is a question event: X5 = 495670, Y5 = 923276, Z5 = 11 
event 6 is a question event: X6 = 470996, Y6 = 847307, Z6 = 20 
event 7 is a question event: X7 = 332590, Y7 = 350288, Z7 = 19 
event 8 is a question event: X8 = 835836, Y8 = 956430, Z8 = 19 
event 9 is a grow event: U9 = 5, V9 = 18 
event 10 is a grow event: U10 = 2, V10 = 12 
event 11 is a question event: X11 = 180886, Y11 = 720572, Z11 = 11 
event 12 is a grow event: U12 = 7, V12 = 16 
event 13 is a grow event: U13 = 12, V13 = 9 
event 14 is a grow event: U14 = 13, V14 = 14 
event 15 is a question event: X15 = 401440, Y15 = 654179, Z15 = 19 
event 16 is a question event: X16 = 57969, Y16 = 573047, Z16 = 4 
event 17 is a question event: X17 = 496283, Y17 = 519411, Z17 = 2 
event 18 is a grow event: U18 = 2, V18 = 9 
event 19 is a grow event: U19 = 16, V19 = 1 
event 20 is a grow event: U20 = 6, V20 = 18 
event 21 is a grow event: U21 = 18, V21 = 8 
event 22 is a question event: X22 = 859374, Y22 = 941997, Z22 = 8 
event 23 is a question event: X23 = 137037, Y23 = 414289, Z23 = 15 
event 24 is a grow event: U24 = 8, V24 = 9 
event 25 is a question event: X25 = 81050, Y25 = 720752, 
Z25 = 12 

val1 = 0 
val2 = 68241 
val3 = 0 
val4 = 0 
val5 = 32580 
val6 = 244929 
val7 = 0 
val8 = 13592 
val9 = 0 
val10 = 0 
val11 = 345651 
val12 = 0 
val13 = 0 
val14 = 0 
val15 = 623327 
val16 = 408310 
val17 = 46258 
val18 = 0 
val19 = 0 
val20 = 0 
val21 = 0 
val22 = 165248 
val23 = 125347 
val24 = 0 
val25 = 1780809

Source: hackerearth | Difficulty: HARD
Tags: Data structures


Solutions: