Background

:::info[Problem Background] The ground in the woods was covered with dead leaves that had piled up over the years, making a light, dry crunch when stepped on. Tall conifers stretched straight up into the sky, their branches crossing and cutting the already dim light into scattered fragments. Now and then, wind slipped through gaps in the forest, bringing a faint chill and the smell of grass and trees. Far away, unknown birds could be heard, their calls coming in broken pieces from somewhere deeper inside.

But as time passed little by little, Fern gradually sensed that something was wrong.

Those seemingly unfamiliar roots, the dead log leaning against a stone, and even a small cluster of pale blue flowers blooming in the shade all felt like things she had seen before. After walking a bit further, Stark finally stopped, staring at a gray-white rock not far away with cracks on its surface, his expression stiff.

“This place... have we been here just now?”

Fern was silent for a moment, then nodded softly.

They had not simply taken the wrong path.

This forest was much larger than it looked from the outside. Leaves, mist, nearly identical trails, and even rocks and shadows that seemed to slowly shift their positions wore down their sense of direction bit by bit. No matter which direction they moved in, in the end it was as if something gently pushed them and sent them back to where they started. It was as though the forest itself was quietly watching the intruders, patiently making them go in circles.

“Is it something like a barrier?” Fern asked in a low voice.

“It’s more like some very old disorientation spell.” Frieren looked up at the sky, mostly blocked by the canopy, her tone still calm. “It’s on a huge scale, and it has fused with the forest itself. Forcing it open would be a bit troublesome.”

“When you say ‘a bit troublesome,’ it’s usually not just ‘a bit’...” Stark sighed and set down the long axe on his back.

After circling for a long time, the three finally decided to stop and rest for a while. Fern sat against a moss-covered tree root and gently placed her water bottle by her side. Stark sat directly on a flat rock, tilted his head back, and let out a long breath. The wind in the woods still moved slowly through the trees. Leaves rubbed against each other, making a faint, repetitive rustling sound that made it hard to tell how much time had passed.

Frieren did not sit down right away.

She half-kneeled on a slightly open patch of ground, took out her notebook, and quietly drew the route they had taken bit by bit. The forked paths, the rocks that appeared again and again, the trees they had marked, and the trail that looped around and finally connected back to the starting point were all marked on the pages with simple and clear lines. The drawing became more and more complicated, like a bundle of tangled threads with no exit.

Fern leaned over to take a look and said softly, “It’s already turned into this...”

“Yeah.” Frieren closed the notebook. “But now, at least we can figure out how we got trapped.”

She finally sat down beside the other two, lightly tucking the pen back between the pages. Her silver-white hair fell along her shoulder. The air in the forest was so quiet it almost felt still. Since they could not find a way out for the moment, there was no point in rushing forward in anxiety.

“So what do we do next?” Stark asked.

Frieren thought for a moment, looked at the route map she had just drawn, and suddenly smiled very lightly.

“Let’s rest for a while first.” She said. “And by the way, let’s play a game.” :::

Problem Description

The map drawn by Frieren can be seen as an undirected graph $G$ with $n$ vertices and $m$ edges, where the vertices are numbered from $1$ to $n$. In addition, Frieren has a sequence of length $k$: $a_1, a_2, \dots, a_k$, where $a_i \in [1,n]$. Fern and Stark need to play $q$ rounds of a game on the map and the paper strip in turns.

In each round, Frieren gives an interval $[l,r]$ where $1\leq l\leq r\leq k$, representing the scope of the current game. In the game, each player moves the same token in turns, and the token starts at position $l$. If the token is currently at position $i$, then it can be moved to position $j$ if and only if $i < j \leq r$, and there exists a path from $a_i$ to $a_j$, and the length of the path has the same parity as $j-i$.

Note that a path here is defined as a sequence of vertices $\{v_1, v_2, \dots, v_t\}$. For any $i\in[1, t)$, there is an edge between $v_i$ and $v_{i+1}$. Vertices may repeat; in other words, a path is allowed to pass through repeated vertices or edges. The length of a path is the number of edges it passes through, i.e. $t-1$.

If a player cannot make any legal move, then that player loses. For each game, Frieren wants to know who will win if both sides play optimally. Fern moves first.

Input Format

The first line contains four integers $n,m,k,q(1\leq n,m,k,q\leq 2\times 10^5$, representing the number of vertices in the map, the number of edges, the length of the sequence, and the number of game rounds.

In the next $m$ lines, each line contains two integers $u,v(1\leq u,v\leq n)$, meaning there is an undirected edge $(u,v)$ between $u$ and $v$.

Next are $k$ integers $a_1,a_2,\dots,a_k(1\leq a_i\leq n)$, representing the sequence $a_1, a_2, \dots, a_k$.

In the next $q$ lines, each line contains two integers $l,r(1\leq l\leq r\leq k)$, representing the range $[l,r]$ of one game.

Output Format

Output $q$ lines. Each line contains a string Fern or Stark, meaning the winner is Fern or Stark.

5 4 5 4
1 2
2 3
3 1
4 5
1 4 2 5 3
1 5
2 5
3 4
4 5

Fern
Stark
Stark
Stark

Hint

For Sample 1, it is not hard to see that for the vertex set $\{1, 2, 3\}$, no matter how you choose the start and end points, you can always find one legal path of odd length and one legal path of even length. $4\to 5$ and $5\to 4$ are also two legal paths of odd length, but you cannot find an even-length path. Other than that, there are no other paths.

So consider the four games. In the first game, the paper-strip sequence interval is $[1, 5]$, i.e. $\{1, 4, 2, 5, 3\}$. It is not hard to see that since there is an even path for $1\to 3$, and $5 - 1 = 4$ is also even, Fern can directly move the token from index $1$ to index $5$, and Stark cannot continue to move.

In the second game, the paper-strip sequence interval is $[2, 5]$, i.e. $\{4, 2, 5, 3\}$. It is not hard to see that the token cannot make any move, because there is no path for $4\to 2$ or $4\to 3$. Also, for $4\to 5$ there is only an odd path, which has different parity from $3 - 1 = 2$.

In the third game, the paper-strip sequence interval is $[3, 4]$, i.e. $\{2, 5\}$. There is no path between the two points, so the token cannot make any move.

In the fourth game, the paper-strip sequence interval is $[4, 5]$, i.e. $\{5, 3\}$. There is no path between the two points, so the token cannot make any move.

In summary, only in the first game can Fern win. In the last three games, since the token cannot move at the start, Stark wins all of them.

Translated by ChatGPT 5