E - Enjoy the Chat Group

Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)

You're working on a read notifications feature for your very popular group chat app. The main idea is to show a small rounded icon containing the viewer's profile picture below the messages they have read. Given that everyone is eventually expected to read all messages, your team decided on the following rules for the feature:

  • There can never be duplicated icons among the messages.
  • If a viewer has read multiple messages, their icon will be docked to the last message (in chronological order) that they read.
  • If multiple icons must be displayed for any particular message, then they will be displayed in sorted order by the viewers' ids.
  • A viewer cannot ever see their own icon in any message.
You know the time at which each message is sent. You may assume that communication is perfect and that every message is delivered to every user at exactly the same time. Given an access time $T_q$ and a viewer $V_q$, return the ids of the users whose icons must be shown to user $V_q$ for the message that was sent closest to the access time $T_q$.


The first line contains the number of messages $n$ ($1 \leq n \leq 2 \times 10^5$) that were sent in the group and the number of users $v$ ($1 \leq v \leq 2 \times 10^5$) in the group.

The second line contains $n$ sorted distinct integers $tm_i$ ($1 \leq tm_i \leq 10^9$). The $i$-th of them represents the time at which the $i$-th message was sent.

The third line contains the number of accesses to the group's messages $m$ ($1 \leq m \leq 2 \times 10^5$). 

The next $m$ lines contain two space-separated integers $v_i$ ($1 \leq v_i \leq v$) and $t_i$ ($1 \leq t_i \leq 10^9$) representing that the $i$-th access was performed by viewer $v_i$ at time $t_i$.

The last line contains two space separated integers $V_q$ ($1 \leq V_q \leq v$) and $T_q$ ($1 \leq T_q \leq 10^9$): $V_q$ is the viewer for which we must display read notification icons and $T_q$ is the time at which this viewer accesses the group chat.  Note that this access may or may not appear in the list $m$ of accesses described above.}


Print $K$ space-separated integers in ascending order in a single line. They correspond to the ids of the $K$ viewers whose read notification icons must be shown for the message closest in time to $T_q$ for the given viewer. If there are no ids to write, print "Nothing to display".

Sample test(s)

5 3 1 3 5 7 11 7 1 2 1 3 1 4 2 3 2 5 3 1 3 2 1 4
5 3 1 3 5 7 11 7 1 5 1 6 1 7 2 1 2 2 2 3 3 11 2 1
Nothing to display
6 5 1 2 3 5 8 13 7 4 8 4 9 4 10 1 8 2 8 3 10 5 8 1 9
2 4 5