Social Media Hashtag Query

You are given a series of actions that simulate posts and queries on a social media platform. Each post action has a timestamp and a message that may contain one or more hashtags (words starting with the '#' symbol). Each query action provides a current time and a duration, and asks for the most popular hashtag in the time window from current_time - duration to current_time.

The sliding window behavior implies that for each query, any post with a timestamp earlier than current_time - duration should be ignored. In this window, count the occurrences of each hashtag. If there are multiple hashtags with the same highest frequency, output the lexicographically smallest one. If no hashtags exist within the window, output "None".

Note: You may assume that actions (both posts and queries) are given in non-decreasing order of timestamps.

inputFormat

The first line of input contains an integer n representing the number of actions. Each of the next n lines contains an action.

• A post action has the format: P timestamp message, where timestamp is an integer and message is a string that may include hashtags.
• A query action has the format: Q current_time duration, where both current_time and duration are integers.

Actions are provided in the order they occur.

outputFormat

For each query action, output a single line containing the most popular hashtag in the respective time window. If no hashtags are found in that window, output None.

## sample

7
P 1 This is the first post #hashtag1
P 3 Another post with #hashtag2 #hashtag3
P 5 More #hashtag1 in this post
Q 6 4
P 8 This is a post without hashtag
Q 9 7
Q 9 1

#hashtag1
#hashtag1
None

</p>