The White Rabbit's Pocket Watch

The White Rabbit's pocket watch shows only the hours 0 to 12, and past 12 it returns to 0. When a trip ends, the Rabbit writes down whatever number the pointer rests on. A trip that really took 14 hours leaves the pointer on 1, so his logbook records 1. Every duration in the logbook is therefore the real duration taken modulo 13.

Wonderland has $N$ locations. There is at most one track directly joining two locations, and a track takes the same real time in both directions. The real time of one track is an integer between 1 and 12.

The logbook holds $T$ trips. One entry has the time read off the watch, the number of locations passed, and the order in which they were passed. The same location can appear several times. Two locations that are neighbours in the order are joined by a direct track, and the tracks that appear in the logbook are all the tracks of Wonderland.

Alice is at location $A$ and wants to reach the Rabbit's hole at location $R$. Find the smallest real time of a route from $A$ to $R$.

The logbook alone fixes the real time of every track, and at least one route from $A$ to $R$ exists.

The first line contains the integers $N$, $A$, $R$ and $T$ separated by spaces. $N$ is the number of distinct locations, $A$ is the location where Alice is, $R$ is the location of the Rabbit's hole, and $T$ is the number of trips written in the logbook. Locations are numbered from 1 to $N$.

Each of the next $T$ lines describes one trip in the format d p a1 a2 ... ap, where $d$ is the trip time the Rabbit read off the watch, $p$ is the number of locations passed, and $a_1\ a_2\ \dots\ a_p$ is the order in which they were passed.

Print one integer, the shortest real time it takes Alice to reach the Rabbit's hole.

• $2 \le N \le 200$
• $1 \le A, R \le N$
• $1 \le T \le 500$
• $0 \le d \le 12$
• $2 \le p \le 800$
• $1 \le a_i \le N$
• There are at most 200 distinct tracks.
• The real time $d_{ij}$ of one track is an integer with $1 \le d_{ij} \le 12$.