##### Woburn Challenge 2018-19 Round 4 - Senior Division

Billy has been having a great time playing a demo of Nintendo's next
highly-anticpated 3D platforming game, *Super Luigi Odyssey*.

One challenge in the game sees Luigi trapped in a long hallway, which can be represented as a number line with positions increasing towards the rightwards direction. There are platforms in it, with the -th one at position and at a height of metres. No two platforms are at the same position. Luigi begins on platform (note that this is not necessarily the leftmost platform).

Much to Luigi's concern, the hallway is filled with some deadly lava. Initially, the lava reaches up to a height of metres. At any point, a platform is considered to be submerged in lava if the lava's height exceeds the platform's height.

A sequence of events will then occur, each having one of three possible types. The type of the -th event is described by the integer .

- If , then the lava's height will increase by metres. It's guaranteed that this will not cause the lava's height to become negative. If this causes Luigi's current platform to become submerged, then he will immediately perish.
- If , then lasers in a row will be fired at Luigi. Each laser will force him to jump to the next non-submerged platform to the left of his current one. If there's no such platform, then he'll instead be forced to jump into the lava and perish.
- If , then similarly lasers in a row will be fired at Luigi, with each one forcing him to jump to the next non-submerged platform (if any) to the right rather than the left.

Luigi is not allowed to move between platforms aside from being forced to by type- or type- events.

Even if Billy manages to keep Luigi alive through all events, he may not be out of the woods yet — his success in later challenges will depend on how much of Luigi's energy has been spent. Whenever Luigi jumps from platform to platform , he expends units of energy. Note that the amount of energy required doesn't depend on the platforms' relative heights.

Help Billy determine how much energy Luigi will expend throughout all events (if he will even survive that long). As this may amount to quite a few units of energy, you only need to determine the total modulo .

#### Subtasks

In test cases worth of the points, , , and .

In test cases worth another of the points, .

#### Input Specification

The first line of input consists of three space-separated integers, ,
, and .

lines follow, the -th of which consists of two space-separated
integers, and , for .

lines follow, the -th of which consists of two space-separated
integers, and , for .

#### Output Specification

Output a single integer, the total number of units of energy which Luigi
will expend (modulo ), or `-1`

if he will be forced to touch
the lava and perish at any point.

#### Sample Input 1

```
5 7 1
4 4
5 5
13 6
0 8
10 8
3 1
1 4
2 1
1 -1
3 4
1 2
2 2
```

#### Sample Output 1

`32`

#### Sample Input 2

```
2 2 2
0 2
1 1
1 1
3 1
```

#### Sample Output 2

`-1`

#### Sample Explanation

In the first case, Luigi will be forced to jump along the follow sequence of positions:

- Event 1:
- Event 3:
- Event 5:
- Event 7:

In total, these jumps require units of energy (which is equal to modulo ). If were equal to rather than , then units of energy would be required instead.

In the second case, after the lava's height is raised to metres, Luigi will have no non-submerged platform to jump to on his right, and so will be forced to jump into the lava and perish.

## Comments