The finals in the Striker-Count competition are
finally starting. All the members of ICPS have arrived and the
pizza is served. Atli decided to watch the finals despite not
being familiar with Striker-Count. So Atli gets Bergur
to explain the rules to him.
In Striker-Count two teams of five compete. One of
the teams is called the blue team and the other is the yellow
team. The teams then switch colors at halftime. The team that
wins the game gets a point, and the first team to two point
wins the match. Each match is played on a different map. There
are two bomb sites on each map, which the blue team has to
defend from the yellow team. The goal of the yellow team is to
plant a bomb on the bomb sites. The bomb takes seconds to explode, during which
the yellow team has to make sure the blue team doesn’t defuse
the bomb. The yellow team gets a round win if the bomb
successfully explodes. If one team successfully eliminates the
entirety of the other team it wins the round. Finally, the
yellow team loses if they don’t plant the bomb or eliminate the
blue team in two minutes. The first team to win round wins the map and halftime
is after rounds. If
the final score is , there is overtime. Atli
quickly realizes that the players run to the same locations at
the start of each round. Bergur explains to him that the
players have to hurry up to get to these locations because it
takes the teams almost the same time to get there. Bergur calls
these locations contact points. However, Atli notices
that it doesn’t always take the same time to get to a location.
Bergur tells him that sometimes the players spawn in a more
favourable spot, some players are better at the movement
mechanics in the game, and your base movement speed depends on
which weapon you are carrying. Atli therefore thinks it makes
more sense to define possible contact points. Each map
can be described as a directed, weighted graph. The existence
of an edge from to
with weight
implies a path on the
map from point to
that takes on average
time to traverse. Each
edge also has a deviance . If the weight of is it takes at least time to traverse the
path and at most . Atli then defines a point on the map as a possible
contact point if there exists for each edge
such that the point
becomes a contact point in the graph with precisely the weight
for edge
. An edge is a contact
point in a graph if the shortest paths from each team’s
starting points to that point are equal. Which points are
possible contact points.
The graph from sample
Input
The first line of the input includes two integer,
and with . These
integers represent the number of points on the map and the
number of paths, respectively. The next line on the input
includes two integers
and , with . The number
gives the starting
point of the blue team and gives the starting point of the
yellow team. It is guaranteed that . The next lines include four integers
, with
,
. They represent a path from to on the map taking on average
time with deviance
. It is
guaranteed that the graph includes no self loops and each
pair appears at
most ones in the input.
Output
The output should include those points the are possible
contact points, in increasing order, on one line. If there are
no possible contact points print ‘Thessi leikur verdur
sennilega leidinlegur’.
Sample Input 1 |
Sample Output 1 |
5 6
1 5
1 2 5 2
1 3 1 1
1 4 2 1
3 4 1 1
5 2 2 1
5 4 5 1
|
2
|
Sample Input 2 |
Sample Output 2 |
4 4
1 4
1 2 10 1
1 3 5 1
4 2 5 1
4 3 10 1
|
Thessi leikur verdur sennilega leidinlegur
|
Sample Input 3 |
Sample Output 3 |
13 38
2 10
1 2 2 1
1 11 7 2
1 5 4 1
2 1 2 1
2 3 3 1
3 2 3 1
3 7 2 2
3 4 6 1
4 3 6 1
4 8 7 2
5 1 4 1
5 2 1 1
5 6 4 2
6 5 4 2
6 7 1 1
6 9 8 3
6 12 10 4
7 3 2 2
7 8 8 2
7 9 10 3
8 4 7 2
8 7 8 2
8 10 13 2
9 6 8 3
9 7 10 3
9 10 3 1
9 12 4 2
10 8 16 5
10 9 3 1
10 12 4 2
11 1 7 2
11 12 4 1
11 13 1 1
12 6 10 4
12 9 4 2
12 10 4 2
12 11 4 1
13 11 1 1
|
6 7 8 11 13
|