Itzel is very excited because her friend group organized a "ladies brunch" at the new aesthetic restaurant in town: La Cafetería Orgánica De Especialidad: Frappés, Éclairs y Matcha (CODEFEM). She woke up at 9:00, had breakfast at 10:00, went to the gym until 12:00, got ready, and arrived on time at 15:00.

Itzel and her friends sit around a circular table in clockwise order, where Itzel occupies position $$$0$$$ and her friends occupy positions $$$1, 2, \dots, N-1$$$.

The cafe has a menu consisting of $$$M$$$ products with fixed integer prices. As the afternoon progresses, they start ordering drinks and desserts. Seeing that the waitress is overwhelmed by the high volume of orders and is having trouble keeping track of everyone's bill, Itzel decides to write a program to process the orders.

There are $$$Q$$$ operations of three types:

• 1 PersonName ProductName: The specified person orders a product from the menu.
• 2 L R ProductName: Everyone seated in the clockwise circular range from position $$$L$$$ to position $$$R$$$ ($$$0 \le L, R \lt N$$$) orders the specified product. If $$$L \le R$$$, this covers positions $$$L, L+1, \dots, R$$$. If $$$R \lt L$$$, this wraps around the circular table, covering positions $$$L, L+1, \dots, N-1$$$ and $$$0, 1, \dots, R$$$.
• 3 PersonName: The waitress queries the total accumulated bill for the specified person.

Help Itzel process all operations and output the answers to all queries.

Emily is very excited to lead a project for the first time, especially one as inspiring as CODEFEM! However, as she quickly learned: "With great power comes great responsibility... and tons of meetings!".

There are meetings scheduled with the marketing team, design team, problem setters, finance, and logistics. As a dedicated leader, Emily wants to attend as many meetings as possible. She has a list of $$$N$$$ scheduled meetings. Each meeting $$$i$$$ has a start time and an end time specified in 24-hour format (HH:MM).

The scheduling rules are as follows:

• All meetings start during the current day (between 00:00 and 23:59).
• Emily must attend each chosen meeting from start to finish.
• She cannot be in two meetings at the same time.
• A meeting may cross midnight: if its end time is less than or equal to its start time, the meeting ends on the following day.
• If one meeting ends exactly when another starts, Emily may attend both.

Help Emily organize her agenda and find the maximum number of meetings she can attend.

Celi and Itzel decided to start their fitness journey. They bought matching outfits and trendy water bottles, but couldn't afford a personal trainer, so they turned to TikTok. There they found Coach Emily, whose main training philosophy is: "The gym isn't about how much weight you lift, but about the aura you radiate".

According to Coach Emily's philosophy:

• There are $$$N$$$ different exercises, numbered from $$$1$$$ to $$$N$$$.
• On each of the $$$Z$$$ training days, Celi and Itzel can choose to perform exactly one exercise or take a rest day.
• If they choose to perform exercise $$$i$$$ on day $$$c$$$ of a consecutive streak of that same exercise:
  • If $$$c \le d_i$$$: they gain $$$+k_i$$$ aura points.
  • If $$$c \gt d_i$$$: they gain $$$+(k_i - x_i)$$$ aura points (the penalty $$$x_i$$$ applies for each consecutive day that exceeds the optimal limit $$$d_i$$$).
• If they choose to rest, they gain $$$0$$$ aura points and any active streak is reset to $$$0$$$.
• If they switch from exercise $$$i$$$ to a different exercise $$$j \ne i$$$, the streak for exercise $$$j$$$ starts at $$$1$$$.

Initially (before day 1), they have no active streak. Celi and Itzel want to know the maximum amount of aura points they can accumulate by the end of the $$$Z$$$ training days if they choose their daily activities optimally.

Your team will have an important mission after the contest: You have to set up a new playground for a couple of the beloved pets of Code Fem: two extremely cute guinea pigs. For that reason, your team needs to buy decorative lights of different colors to embellish the place. Each light is only one color.

The decorative lights are distributed all over the surface where the playground is to be built by your mates; however, you had to go to the bathroom and did not get to know the arrangement of the lights. Your peers have noticed that they could join the lights with imaginary straight lines and create polygons whose vertices are those lights themselves. After thinking a lot about the topic, they came up with a question that challenged you to solve: Regardless of the arrangement they chose, and the colors of lights they utilized, how many vertices does the largest polygon that you can guarantee have, such that all the vertices (lights) are the same color? It does not matter what color it is.

In this case, consider that the more vertices a polygon has, the greater it is, regardless of its area. Moreover, the polygon could be convex or non-convex. You can be sure there are no three collinear lights.

Mitzi is about to leave for CODEFEM when she notices a little lizard wandering around her patio. The problem is that her $$$k$$$ chubby cats live there too.

Mitzi's patio is an $$$n \times m$$$ grid of tiles. The lizard starts on tile $$$(s_x, s_y)$$$ and can move only to the tile directly above, below, to the left, or to the right, without leaving the patio.

Each chubby cat $$$i$$$ is sitting on tile $$$(x_i, y_i)$$$ and has a jumping range $$$f_i$$$. No matter how lazy a cat may be, if the lizard is at a Manhattan distance less than or equal to $$$f_i$$$, the cat can catch it in a single leap. Therefore, the lizard will never step on a tile within the reach of any cat.

The Manhattan distance between two tiles $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as:

$$$$$$|x_1-x_2| + |y_1-y_2|$$$$$$

and represents the minimum number of moves required to travel from one tile to the other using only the four main directions.

Luckily for the lizard, there are $$$h$$$ tiles with holes in the patio where it can hide. As soon as it reaches any of them, it will be safe.

Among all holes that the lizard can reach without ever stepping on a tile within the jumping range of a cat, it will choose the one that requires the fewest moves.

If several holes can be reached using the same minimum number of moves, the lizard will choose the hole with the smallest row number. If there is still a tie, it will choose the one with the smallest column number.

Mitzi wants to know which hole the lizard will reach, so she can decide whether she can leave peacefully or needs to help it escape.

Determine the tile containing the hole the lizard will reach.

If there is no safe path to any hole, print $$$-1$$$ $$$-1$$$.

After CODEFEM, Ashley decides to celebrate by visiting some of the cafes located near the event.

There are $$$N$$$ cafes arranged along the same street, numbered from $$$1$$$ to $$$N$$$. At cafe $$$i$$$, Ashley can buy a drink that costs $$$a_i$$$ coins.

Ashley wants to visit a consecutive group of cafes and buy exactly one drink at each cafe she visits.

She has a budget of $$$B$$$ coins.

Find the maximum number of consecutive cafes Ashley can visit without spending more than $$$B$$$ coins.

If Ashley cannot afford a drink at any cafe, the answer is $$$0$$$.

After a long day at CODEFEM, the organizers prepared several trays of macarons for the participants.

There are $$$N$$$ trays arranged from left to right on a conveyor belt. The $$$i$$$-th tray initially contains $$$a_i$$$ macarons.

The conveyor belt can only move macarons to the right. In one operation, you may choose a tray $$$i$$$ ($$$1 \le i \lt N$$$) that contains at least one macaron, and move exactly one macaron from tray $$$i$$$ to tray $$$i+1$$$.

The organizers want every tray to contain exactly the same number of macarons.

Determine whether this is possible.

If it is possible, print the minimum number of operations required to make all trays contain the same number of macarons.

Otherwise, print $$$-1$$$.

After a long day of preparing everything for CODEFEM, the organizers decided that everyone deserved a cupcake.

There are $$$N$$$ tables at the event. At table $$$i$$$, there are $$$a_i$$$ people sitting.

The organizers bought $$$C$$$ cupcakes, and every person should receive exactly one cupcake.

Determine whether there are enough cupcakes for everyone.

• If there are enough cupcakes, print YES followed by the number of cupcakes remaining.
• Otherwise, print NO followed by the number of additional cupcakes needed.

Alejandra is determined to prepare the best Christmas fruit punch in history this year. For that reason, she is starting with her plan at this point of the year. To do so, she has bought many ingredients that she planned to use for experimenting and trying all possible recipes until she finds the ideal one: the holy grail of Christmas punches.

When she arrived at his family's home with all his ingredients, her sister caught her early Christmas spirit and decided that she also wanted to prepare her own punch. She asked Alejandra to sell her some of the ingredients she had bought. Alejandra agreed, on the conditions that both of them use everything they choose and that they use different ingredients, for example, if one of them uses apples in her recipe, the other cannot use them.

Furthermore, Alejandra's sister has a limited budget and can only buy $$$k$$$ ingredients (Alejandra and her sister agreed that all ingredients would have the same price). However, she is certain that this will be enough to make a memorable punch for her friends.

Alejandra is really meticulous when it comes to cooking, so she wants to take some time to evaluate the possibilities that she could prepare. To do so, she first needs to know how many recipes she will have to assess. The problem is that Alejandra is a star in the kitchen, but terrible at doing calculations, so she needs your help to determine how many recipes can be prepared without the $$$k$$$ items she sold to her sister.

March 8th (8M) is a very important date for any woman, and Mar knows it. Although she felt very nervous about attending a march, she was always drawn to it, and this year she finally dared to go for the first time, motivated by her group of friends.

Upon arriving, she was amazed by the huge number of women filling the streets, and then she noticed something special: some women held ribbons tied to another's wrist, and some had ribbons tied back, representing their union. If a girl $$$A$$$ tied a ribbon to a girl $$$B$$$, then following the ribbons, $$$A$$$ can reach $$$B$$$, and from $$$B$$$ she can keep going to every woman that $$$B$$$ reaches.

Mar considers a group of women to be united if, following the direction of the ribbons, every member can reach every other member.

Mar notices that, although there are many ribbons, the women of the march are not united. She wants to know the minimum number of additional ribbons that must be tied so that all the women in the march form a single united group.

Ada and Grace have been friends for a long time, but there is one thing they have never been able to agree on: what makes a message funny.

To settle the argument once and for all, each of them created a collection of JajaScript rules. Each rule describes a pair of expressions that, when they appear in a message, contribute to its funniness score.

A rule consists of two non-empty strings $$$A$$$ and $$$B$$$, and an integer $$$P$$$, the funniness rating of the rule.

Suppose that $$$A$$$ occurs $$$x$$$ times in the message and $$$B$$$ occurs $$$y$$$ times. Then this rule contributes $$$x \cdot y \cdot P$$$ points to the owner's total score.

All occurrences are counted, including overlapping occurrences. For example, the string aa occurs three times in aaaa.

The score of Ada (respectively, Grace) is the sum of the contributions of all of her rules. Rules are considered independently: the same expression may appear in several rules, the same rule may appear more than once, and $$$A$$$ may be equal to $$$B$$$.

Given the message and both collections of rules, determine whose JajaScript score is greater.

Frances has two great passions: programming and cross-stitching. Naturally, she eventually found a way to combine them.

She is working on a program to improve a long embroidery design. The design is represented by a string $$$b$$$, divided into sections by spaces. Each lowercase English letter represents the color of one stitch. For example, $$$p$$$ may represent pink, $$$g$$$ green, and $$$b$$$ blue; the actual colors are not important to Frances' program.

Frances has ten favorite embroidery patterns. Each pattern is represented by a string and has a beauty value:

A section can be turned into one of Frances' patterns if both strings have the same length and differ in exactly one position. Frances can then replace the stitch at that position and gains the beauty value of the resulting pattern.

If a section is already exactly equal to any of Frances' favorite patterns, Frances leaves that section unchanged. It cannot be modified and gives no beauty points.

If a section can be turned into more than one pattern, Frances only considers the pattern with the highest beauty value.

Replacing stitches that are too close to each other may deform the fabric. Therefore, if Frances replaces stitches at absolute positions $$$p_1$$$, $$$p_2$$$, ..., the distance between any two selected positions must be at least $$$x$$$.

Positions are 0-indexed and refer to the complete string $$$b$$$. Spaces also occupy positions in the string, although a space can never be replaced.

Help Frances determine the maximum total beauty she can obtain.