#!SUITS

Problem 1 – Decryption

As you pass through the intergalactic gateway posing as the door to lab 117 only one thought crosses your mind – ‘Here we go again…’.

When your vision stabilises you see a small table in front of you with some paper on it. Part of the text on the page looks like english but then there is a long line of nonsense at the end. Looking closer you read:

To escape this room you will need to follow the encrypted instructions below. Don’t recognise the encryption scheme? Well read on then.

I started with plaintext and jumbled it up to produce the ciphertext. To do this I generated a sequence of numbers, then one at a time I took the next number in the sequence and counted that many places along my plaintext (looping back to the start if necessary). The letter I got to was removed and added to the ciphertext. This process was repeated until all the letters in the message had been used up.

The sequence was generated as follows:

• I started with 1, 2, 1
• To generate the next number I added the previous number to the number three previous (for example, to get the fourth number I added 1 and 1, getting 2)
• If the number just generated was larger than 1000, instead I took the number mod 1000 (so 1025 became 25)
• Once N numbers were generated I stopped and reversed the entire list

After reading all the text you whip out your trusty laptop and start coding.

Input

The first line will contain a single number, ‘N’, whch indicates how many numbers in the sequence to generate before reversing it. The second line will contain a line of text, composed of only lowercase characters (’a-z’).

Output

Your program should print a single line to stdout – the decrypted message.

Sample Input

6 olehl

Sample Output

hello

Problem 2 – Portal mania

Once decrypted, the message describes how to escape the room you are in. It turns out that this room is one of many in a long row, and the table is in fact a portal device with controls on its underside.

The controls consist of a series of buttons, each of which will take you forward a certain number of rooms. Also, rather than draining power when pressed, the buttons will add a certain amount of power. To escape you need to get as much power as possible once you reach the final room in the row, allowing you to activate a special button that will hopefully take you away from this nightmare.

Input

The first line of input will contain two integers, B and R. B is the number of buttons on the machine (0 < B < 10,000). R is the number of rooms (0 < R < 10,000).

Following this will be B lines, each describing a single button. Each line will have two numbers, the distance the button will take you forward and the amount of energy it will add to the portal machine in the process. You are gauanteed that one button will be present that takes you forward one room, but provides no extra energy.

Output

You must produce a single number, the maximum amount of energy the machine can have when you reach the final room.

Sample Input

3 9 1 0 3 4 4 5

Sample Output

12

One entrance, many exits

After pressing the special button you find yourself standing in a room with a bunch of other suits members, K of you in total. There are a number of exits from the room and a map on one wall. Looking at the map you see a ‘you are here’ marker on one point and a bunch of the other points are marked as exits.

The map also kindly informs you that while everyone may walk around as much as they like, each exit will only accept one person. Also, a timer starts as soon as the first person leaves this room. If you don’t choose the optimum set of exits and travel to them by the shortest routes, you will still be here when the place explodes.

You tell everyone what the map says and then get to work figuring out which K exits to use and how to get to them.

Input

The first line will contain five numbers, N, L, K and E, S. These are:

• The number of rooms, 0 < N < 1,000,000
• The number of links between rooms, 0 < L < 1,000,000
• The number of suits members escaping, 0 < K < N
• The number of exits, 0 < E < N
• The starting room, S, 1 <= S <= N

Following this will be L lines, each describing a single link with three numbers, the starting point, the ending point and the length (all integers).

Following this will be E lines, each with a single integer, signifying that that point is an exit

Output

You must produce K lines each containing a series of numbers describing a path to an exit.

Sample Input

5 6 2 3 0 1 2 10 1 3 12 3 4 10 2 4 10 4 5 1 1 4 1 2 3 5

Sample Output

1 2 1 4 5