Shakespeare the Tenth has grown bored of writing plays and sonnets all day and wants to get into painting. However, he feels that painting with color is not very artistic, and instead, he wants to paint with letters.

One day, he finds a $$$N \times N$$$ canvas in his basement and starts his painting career. $$$(0, 0)$$$ is the top-left corner of the canvas, and $$$(N-1, N-1)$$$ is the bottom-right corner. A letter takes up a $$$1 \times 1$$$ region and must be aligned on whole number coordinates. As he begins painting, he realizes that a 3D-like effect can be created by stacking letters on each other. Furthermore, he discovers that some letters look better in a given stack and would like these letters to have a majority (making up strictly more than half of the letters) count, which makes it a beautiful stack.

Shakespeare the Tenth decides to paint conduct $$$Q$$$ painting operations, one at a time. One operation is to paint a letter onto a spot in the canvas, which adds it to the top of its stack. Unfortunately, he is not very good at keeping track of his 3D painting and might also ask you to help him determine whether a stack is beautiful. As an inexperienced painter, he might change his mind a lot; therefore, he might like one letter more than the other for a given stack across different queries. In addition, he might choose to remove the top letter of a stack at any given time. If he decides to remove from a stack that he never began painting, it does not do anything. Can you help Shakespeare the Tenth create his favorite painting?

While searching for an open room in the GDC, Macbeth discovers three witches. They prophesy that he will be the highest rated CodeForces competitor at UT.

Elated, Macbeth devises a masterful plan to fulfill the witches' prophecy. Instead of training on CodeForces to improve his rating, he'll gain access to the UT database and forcefully graduate students rated equal to or higher than him.

Macbeth has a list of all the CodeForces accounts connected to UT students, but he doesn't know who's behind each username. He knows the CodeForces usernames of only his friends, who know the CF usernames of only their friends. The network of who knows each other's usernames can be represented as a tree with $$$N$$$ nodes, with Macbeth at node 1. This tree spans all the competitive programmers at UT.

For Macbeth to learn more usernames, he must ask someone whose username he already knows, and this person will tell Macbeth all the usernames they know. Output the minimum number of asks Macbeth must make for him to learn of everyone who has a rating greater than or equal to his.

William recently started studying Shakespeare in his high school English class. However, he is having trouble understanding old English. Every time he comes across an old English word, he searches it up in the dictionary. However, because he has a bad memory, he can only remember the most recent word he searched for.

To help others who struggle with old English, he plans to rewrite all of Shakespeare using modern English. He is very organized and would like to rewrite each word and sentence in order. His friend Anne wants to support him on his journey and has offered to memorize one word for him. If Anne memorizes a word, then William will not have to search it up and can ask Anne instead.

William wants to figure out which word he wants Anne to memorize. As such, for every word $$$w_i$$$, he wants to know how many searches he would have to perform if Anne memorized $$$w_i$$$, and he needs your help.

Shakespeare is writing a new play, but he's struggling to think of what word to use next, so he wants to invent one! To do this, he will start with a given word $$$s$$$, and will perform the following operation any number of times:

• Choose an index $$$i$$$ ($$$1 \leq i \leq n - k$$$) and swap the characters in $$$s$$$ at indices $$$i$$$ and $$$i+k$$$.

Shakespeare wants to know how many distinct words he can construct after any number of operations (possibly none). Unfortunately, Shakespeare doesn't have a computer and he is low on time, so he needs you to do this for him. Since there may be many strings, output this number modulo $$$10^9+7$$$.

Cyrano, upon facing Roxane, is elated to have delivered a poetic declaration despite his internal doubts. Soon, another challenge rises in the shape of her now angered suitors. As Cyrano's only weakness is a superficial one, for every parry he swiftly makes a ballade. When he ends the refrain, his sword will have swiftly ended their courage's bane.

Cyrano currently distributes the pastries from Ragueneau's bakery to families around town. There are $$$N$$$ bakeries labeled $$$1$$$ through $$$N$$$, and $$$M$$$ community bakery mailboxes numbered $$$1$$$ through $$$M$$$. Cyrano must make $$$N$$$ total trips, one trip for each bakery, and for each trip he can choose to arrive at a mailbox of his choice. We denote the position of the $$$ith$$$ bakery by $$$x_i$$$ $$$(1\leq i\leq N)$$$, and the position of the $$$jth$$$ mailbox by $$$y_j$$$ $$$(1\leq j\leq M)$$$.

Initially, Cyrano starts from a bakery $$$x_i$$$. From there, traveling from point $$$x_i$$$ to $$$y_j$$$ requires fighting off $$$x_i\cdot y_j$$$ suitors. Upon arriving at destination mailbox $$$y_i$$$, Cyrano is greeted with a horde of $$$k_i$$$ angry suitors (mailboxes can be repeated, in which case $$$k_j$$$ suitors must be fought again). Since he does not want to overwork his sword, Cyrano would prefer to take on the minimum number of total suitors.

Please compute the minimum number of suitors Cyrano has to defeat, modulo $$$10^9+7$$$, to complete his deliveries.

Shakespeare is writing a soliloquy for his newest play. The soliloquy is represented as a string of $$$N$$$ characters. Shakespeare has a set of $$$M$$$ distinct words where the sum of the word lengths for all words in the set is no greater than $$$10^5$$$. Shakespeare has $$$Q$$$ intervals that cover some portion of the soliloquy. He wants to know, for each interval, how many substrings in that interval are words in the set.

As Shakespeare, you want to put on a performance of $$$n$$$ different plays! You already have ranked each of the plays from $$$1$$$ to $$$n$$$, where $$$1$$$ is the best and $$$n$$$ is the worst.

For your performance, you will choose some permutation of the different plays. Let $$$p_i$$$ denote the rank of the $$$i$$$th play in the list. For a specific schedule, we call the $$$i$$$th play a disappointment if it is worse than the neighboring two plays, i.e. $$$p_{i - 1}, p_{i + 1} \lt p_i$$$. Note that the first and last plays can never be a disappointment. The total disappointment of a schedule is the sum of the ranks of every disappointment play.

You are fine with any schedule as long as the disappointment is not greater than some threshold $$$k$$$. Could you count how many valid schedules exist. Because there may be many such schedules, output the answer mod $$$998244353$$$.

To write a truly thrilling story, one needs to have a set of literary themes. Shakespeare is well-versed in using literary devices in his stories to establish thematic connections between the various subplots of his plays.

We represent one of Shakespeare's works as a graph, where the nodes represent literary themes (love, greed, nihilistic optimism, etc.), and edges represent literary devices. When Shakespeare uses a literary device, he draws a (directed) edge from theme $$$u$$$ to theme $$$v$$$.

Shakespeare is worried that his use of literary devices is getting repetitive. Specifically, a literary device between themes $$$u$$$ and $$$v$$$ is repetitive iff it creates a thematic loop between $$$u$$$ and $$$v$$$ (that is to say, it creates a cycle in the graph containing themes $$$u$$$ and $$$v$$$).

Shakespeare has an existing play and some literary devices that he wishes to add to the play, in the form of a list of queries. Each query consists of two nodes $$$u$$$, $$$v$$$ denoting a literary device connecting theme $$$u$$$ to theme $$$v$$$. If this literary device creates a thematic loop between $$$u$$$ and $$$v$$$, output "YES". Otherwise, output "NO". Then, add the literary device to the graph.

Note that Shakespeare only cares about the current two themes $$$u$$$ and $$$v$$$ when considering a query. That is, he does not care about cycles that don't contain $$$u$$$ and $$$v$$$, and you shouldn't consider them when answering.

If you succeed in your task, you will forever be cemented as one of the greatest literary artists of all time!