Super Performance Command Simulation

This problem is about simulating a sequence of commands on a directed acyclic graph (DAG). The graph consists of n nodes and m directed edges. Node 1 represents the stage while the remaining nodes (2 through n) are waiting rooms, each initially occupied by a theater troupe.

It is guaranteed that every node has at least one path to node 1. A command can be issued on a waiting room u according to the following rule:

• If the troupe at node u has not yet performed and there exists a path from u to 1 such that all intermediate waiting rooms (i.e. nodes other than u and 1) have already been emptied (the troupe has left), then the command is valid. In that case, the troupe at waiting room u leaves along that path, performs on stage and then exits permanently. Note that u itself may still be occupied when the command is issued, but it is allowed to be the starting point.
• If either the troupe at u has already left or no such path exists, then the command is invalid and nothing happens.

You are given a command sequence a1,a2,…,ak (each ai indicates a waiting room when a command is issued) and q queries. Each query is an interval [l, r] meaning that you will simulate the process by executing commands al,al+1,…,ar (in the given order) on a fresh graph where every waiting room initially has a troupe. Your task is to determine how many waiting rooms still have a troupe after executing the selected subsequence of commands.

Note: The simulation for each query is independent. All formulas, such as the one showing the number of nodes n or the condition for the existence of a path, should be interpreted with \( n \) and LaTeX style formulas in the explanation.

inputFormat

The first line of input contains four integers n, m, k and q where n is the number of nodes, m is the number of directed edges, k is the length of the command sequence, and q is the number of queries.

Then follow m lines, each containing two integers u v denoting a directed edge from node u to node v.

The next line contains k integers a1, a2, …, ak representing the sequence of commands (each is a waiting room, i.e. an integer in the range [2, n]).

Then follow q lines, each containing two integers l and r representing a query, meaning that the commands from index l to r (inclusive) are executed in order on a fresh copy of the initial graph.

outputFormat

For each query, output a single integer on a separate line indicating the number of waiting rooms that still have a troupe after executing the specified command subsequence.

sample

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

0
0
0