405429: GYM101962 A Multiset Machine

The mayor of Soteropolis, Betinho, which is known for his exotic tastes and for expending public money on unreasonable things, now decided to buy a Multiset Machine. A Multiset Machine can be represented by a DAG (directed acyclic graph) where each node represents an unary operation and each arc represents data flowing. The type of data that goes through an arc is a multiset of integers.

The incoming arcs of a node represent the input for such operation. If there are multiple incoming arcs, then the actual input for the operation is the sum of the multisets represented by those arcs.

The outgoing arcs of a node represent the output for such operation. The output is a single multiset of integers. If there are multiple outgoing arcs, then this multiset is replicated through all those arcs.

There are 4 types of nodes in a Multiset Machine. Some of them may have restrictions on the number of incoming/outgoing arcs. Also, they may have parameters which are properties of each node.

• source $$$v_1, \dots, v_k$$$ – this node may have incoming arcs or not. If it has, then let $$$I$$$ be the input multiset. Then this node outputs $$$I + \{v_1, \dots, v_k\}$$$. Otherwise, it outputs $$$\{v_1, \dots, v_k\}$$$.
• print – this node has no output. It prints the $$$k$$$-th smallest element of the input multiset. If there is no such element, then it prints -1. There is exactly one node of this type.
• select $$$k_1, k_2$$$ – this node has at least one incoming arc. It outputs a multiset comprised by a range of elements, from the $$$k_1$$$-th smallest element to the $$$k_2$$$-th smallest element of the input multiset. Every other element is ignored. This operation may produce less than $$$k_2 - k_1 + 1$$$ elements if for some $$$k_1 \leq i \leq k_2$$$ there is no $$$i$$$-th smallest element in the input multiset. In particular, if there is no $$$k_1$$$-th smallest element it will output an empty multiset.
• generator $$$a, b, M$$$ – let $$$I$$$ be the input for this node, or $$$\emptyset$$$ if there is no input. This node outputs $$${I + \{ y \;|\; 0 \leq y < M \; \texttt{and} \; \exists x, ax + b \equiv y \mod M \}}$$$.

Every node with no incoming arc is necessarily a source or a generator, and every node with no outgoing arc is necessarily a print. When the machine is turned on, the data starts flowing from the nodes which have no input. A node will only process and output something when all of its inputs have been received. It is also guaranteed that the machine will eventually print something.

Your task is to write a program that, given the structure of the mayor's Multiset Machine, is capable of printing the same number that his machine would print if it was turned on.

The first line contains two integers $$$n, m$$$ ($$$2 \leq n \leq 10^5; 1 \leq m \leq 2 \times 10^5$$$) – the number of nodes and the number of arcs in the graph of the machine, respectively.

The following $$$n$$$ lines contains the descriptions of the $$$n$$$ nodes.

The $$$i$$$-th of these contains first a string representing the type of this node. If it is a source node, then there is a number $$$k$$$ ($$$1 \leq k \leq 10^5$$$) followed by $$$v_1, \dots, v_k$$$ on the same line. If it is a select node, then two integers $$$k_1, k_2$$$ ($$$1 \leq k_1, k_2 \leq 10^{18}$$$) follow. If it is a generator, then three integers $$$a, b, M$$$ ($$$M > 0$$$) follow. If it is a print, then an integer $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$) follow.

Then the following $$$m$$$ lines contains the arcs.

The $$$i$$$-th of them contains integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n; u_i \neq v_i$$$) meaning that there is an arc between $$$u_i$$$ and $$$v_i$$$, in that order.

There may be parallel arcs, but not self-loops.

Every integer which has no constraints specified above are between 0 and $$$10^{18}$$$, inclusive. The sum of $$$k$$$ for every source does not exceed $$$10^5$$$.

Output the integer printed by the machine.

2 1
source 5 1 2 3 4 5
print 4
1 2

4

2 1
generator 2 1 7
print 3
1 2

2

4 3
generator 1 5 4
print 3
select 2 4
source 5 1 2 3 100 1000
1 3
4 3
3 2

2

3 2
source 2 4 5
select 1 1
print 2
1 2
2 3

-1