In the last cycle, the domestic team selection process of ICPC Taoyuan Regional Contest chooses teams from preliminary contests according to the following categories.

• Category 1: Among the teams that participated in the "ICPC Taiwan Online Programming Contest" (TOPC) and solved one problem, the best team from each university will be selected. This category is limited to 30 teams.
• Category 2: The top 40 teams in the "National Collegiate Programming Contest" will be selected.
• Category 3: "Taiwan Private University Programming Contest" qualifies 10 best teams, but no more than two teams per university.
• Category 4: "Taiwan Technology University Programming Contest" qualifies 10 best teams, but no more than two teams per university.
• Category 5: 10 teams will be qualified for their CPE performance, but no more than one team from each university. Such teams must participate in TOPC and solve at least one problem.
• Category 6: If a team of the above five categories resigns for any reason and there are other teams from the same university participating in TOPC. The replacement of the resigning team will be selected from the TOPC participants from the same university according to their performance.
• Category 7: If the total number of teams in the above six categories is less than 100, the organizer will invite the top teams of TOPC to participate in the regional contest. The invited teams must be in the top half of the final standings.
• Category 8: Free to participate, priority will be given to universities not selected in the above categories and will be ranked according to the order of registration.

The domestic team selection rule of ICPC Taoyuan Regional Contest has a major change in the 2023-2024 cycle. The organizer added a note, "If the list of selected teams cannot be submitted 35 days prior to the ICPC Taoyuan Regional Contest, the category will be subject to suspension for that particular year." This change was made to deal with the fact that some preliminaries were held to late. Typically, it takes about five weeks to complete the logistic operations of an ICPC regional contest. Therefore, all preliminaries were held before the end of Octobor, and the regional contests were held in November in the past few years.

The 2023 ICPC Taoyuan Regional Contest will be held from Octobor 21 to Octobor 23, 2023. Consequently, some categories will be suspended if the corresponding preliminaries are still held in late September or Octobor as usual. As the director of TOPC, you must be wise enough to choose a proper date to hold TOPC. If the categories related to TOPC are suspended, there will be much less domestic teams competing in the 2023 ICPC Taoyuan Regional Contest. A contest date is too late for TOPC if it is not at least 35 days prior to Octobor 21, 2023. Please write a program to determine whether a tentative contest date is too late for TOPC.

In recent years, the ICPC community has expanded its global presence, with annual participation encompassing 111 countries, involving 3,450 universities, and engaging 75,000 team members, coaches, and volunteers. However, it is important to note that only approximately 130 teams earn the opportunity to advance to the annual ICPC World Finals. Specifically, for the 2023 ICPC World Finals, only 16 teams from the Asia Pacific Region have qualified. In the 2022 ICPC Asia Pacific Regional Contests, an impressive turnout saw over 1,800 teams representing 283 universities. Regrettably, the vast majority of these teams, more than $$$99\%$$$, were unable to progress beyond the regional contests.

The ICPC Asia Pacific Region has introduced the Asia Pacific playoff as a new tier in the selection process for teams to participate in the 2024 ICPC World Finals. This playoff represents a higher level of competition compared to the regional contests. In 2024, the first Asia Pacific playoff will take place in Hanoi, Vietnam. Approximately 66 teams will earn their spots in this playoff based on the rules outlined in the ICPC Asia Pacific Rules section. This expansion ensures that a greater number of teams will have opportunities to engage in higher-level contests in the coming years.

Due to the introduction of ICPC Asia Pacific Playoff contest, the ICPC Asia Pacific Rules have been changed greatly. After reading the new rules, you find that you are allowed to participate two regional contests in 2023 to have a better chance to advance to the playoff. Your team plans to participate the ICPC Taoyuan Regional Contest and the ICPC Jakarta Regional Contest in 2023. Assume that your team's recomputed team ranks and the site scores of both regional contests are given. Please write a program to determine in which regional contest your team has a better chance of advancing.

(Note: The definition of recomputed team rank and site score can be found in the ICPC Asia Pacific Rules section.)

A monotone sequence is a sequence of numbers that either consistently increases or consistently decreases as you move along the sequence. In other words, it exhibits a consistent trend in either an upward or downward direction.

In a monotone increasing sequence, each term in the sequence is greater than or equal to the preceding term. Mathematically, for a sequence $$$a_1,\dots,a_n$$$, it is monotone increasing if and only if for every $$$1\le i \lt n$$$, $$$a_i \le a_{n+1}$$$. For example, the sequence $$$1, 2, 2, 4, 5$$$ is a monotone increasing sequence because each term is greater than or equal to the previous term.

Monotone sequences are important in various areas of mathematics, including calculus and analysis, as they often simplify the analysis of functions and their behavior. They provide a clear and consistent trend that makes it easier to understand the behavior of a sequence or a function over a range of values.

One of our problem setters is fond of big integers. Over the past few years, the Taiwan Online Programming Contest has frequently featured problems involving big integers. This time, we have a problem that combines big integers with monotone increasing sequences. Your task is to transform a big integer, denoted as $$$x$$$, into a monotone increasing sequence by inserting commas ',' into the gaps between its digits, while adhering to following constraints.

• The last term of the monotone increasing sequence is no more than $$$b$$$.
• Commas cannot be inserted before a zero.
• The number of commas is minimized.

Let's assume that $$$x$$$ is an integer with $$$k$$$ digits and is represented as $$$d_1d_2\cdots d_k$$$. For instance, if we have $$$x=654321=d_1d_2\cdots d_6$$$ and $$$b=1000$$$, we can insert commas into gaps after $$$d_3$$$ and $$$d_5$$$ to convert $$$x$$$ into the following monotone increasing sequence: $$$6, 54, 321$$$.

Please write a program to compute the minimum number of commas required to transform a given big integer $$$x$$$ into a monotone increasing sequence consisting of numbers no more than a given integer $$$b$$$. If there is no way to transform, please print 'NO WAY'.

A polygon is a geometric shape that consists of a closed set of straight line segments connected end-to-end to form a closed loop. These line segments enclose a region of space called the polygon's interior. The points where the line segments meet are called vertices, and the line segments themselves are called edges.

A simple polygon is a polygon that has no self-intersecting edges and has no holes. In other words, none of its edges cross over or intersect with each other within the interior of the polygon, and at each of its vertex, exactly two of its edges meet.

A convex polygon is a specific type of simple polygon that has an additional properties: All interior angles are strictly less than $$$180$$$ degrees. In a convex polygon, if you were to draw straight lines connecting any two points inside the polygon, those lines would always remain inside the polygon.

David has a land with a convex polygon shape that has $$$n$$$ vertices $$$(x_1,y_1),\dots,(x_n,y_n)$$$. He wants to divide the land into two parts by a line segment $$$\overline{PQ}$$$ satisfying the following criteria.

• $$$P$$$ and $$$Q$$$ are points located on different edges of the convex polygon to be divided.
• The two parts are convex polygons with an equal perimeter. That is, the sum of the lengths of the first part's edges equals the sum of the lengths of the second part's edges.

Exponentiation is a mathematical operation that involves raising a base number to a certain exponent to obtain a result. In the expression $$$a^n$$$, where $$$a$$$ is the base and $$$n$$$ is the exponent, it means multiplying $$$a$$$ by itself $$$n$$$ times. The result of this operation is called the exponentiation of $$$a$$$ to the $$$n$$$-th power. For examples, $$$2^3 = 2 \times 2 \times 2 = 8$$$ and $$$5^2 = 5 \times 5 = 25$$$. In these examples, $$$2$$$ is the base, $$$3$$$ is the exponent in the first case, and $$$5$$$ is the base, and $$$2$$$ is the exponent in the second case. Exponentiation is a fundamental operation in mathematics and is commonly used in various contexts, such as solving equations, and cryptography.

In many cryptographic algorithms, particularly those based on number theory like RSA (Rivest-Shamir-Adleman) and Diffie-Hellman, modular exponentiation is a fundamental operation. Modular exponentiation involves raising a base to an exponent modulo a modulus. This operation is computationally intensive but relatively easy to perform, even for very large numbers.

Let $$$x+\frac{1}{x}=\alpha$$$ where $$$\alpha$$$ is a positive integer. Please write a program to compute $$$x^{\beta}+\frac{1}{x^{\beta}}~\mbox{mod}~m$$$ for given positive integers $$$\beta$$$ and $$$m$$$.

An undirected graph is a fundamental concept in graph theory, a branch of mathematics and computer science. It is a data structure that represents a set of vertices connected by edges that have no direction. In other words, in an undirected graph, if there is an edge from vertex $$$u$$$ to vertex $$$v$$$, there is also an edge from vertex $$$v$$$ to vertex $$$u$$$. We use a two-element set $$$\{A,B\}$$$ to represent such undirected edge. An undirected graph is simple if there is at most one edge between any pair of vertices.

In graph theory, a connected component is a group of vertices and edges within a graph where you can travel from any vertex to any other vertex by following a sequence of edges. A bridge is an edge in an undirected graph that, if removed, increases the number of connected components in the graph.

Bridges are essential concepts in graph analysis and have practical applications in network design, fault tolerance, and connectivity analysis. They are often used to identify vulnerable points in a network where the removal of a single edge could lead to the isolation of certain components or the disruption of connectivity. Identifying bridges in a graph can be done using various algorithms which can detect these crucial edges and help analyze the robustness and structure of a network or system.

You have a simple undirected graph whose vertices and edges are $$$V=\{1,2,\dots,n\}$$$ and $$$E=\{\{u_1,v_1\},\dots,\{u_m,v_m\}\}$$$. Your friend, Flora, ask you to sequentially remove edges $$$e_1,e_2,\dots,e_q$$$ from your graph and report the number of bridges left in the graph after each removal. Please write a program to generate the report.

Grigory is a talented engineer who has a love in developing drones and, of course, geometry. As a skilled problem solver, he is able to come up with solutions in difficult situations, but today, he encountered a problem that his abilities alone are not enough to solve. Therefore, as his best sidekick, your task is to assist him.

There are $$$n$$$ cogs on the Cartesian plane. The $$$i$$$-th cog is located at the coordinates $$$(x_i, y_i)$$$ and has a character $$$c_i$$$ that describes its color – "b" means it is a black cog, while "w" means it is a white cog. In addition, no three cogs lie on the same line.

Grigory wants to build a gadget using some cogs. To do this, he first chooses a subset $$$S$$$ that consists of $$$4$$$ or more of the $$$n$$$ cogs. Then, a loop of chains is placed around the cogs. The loop is chosen such that:

• Every cog in $$$S$$$ either touches the loop or lies in its interior.
• The total length of chains is minimal.

For example, the image below shows the chains that would be placed for a chosen set of cogs.

Finally, consider the cogs in $$$S$$$ that touch the loop. These are the most important cogs, so they cannot be interfering with each other. Therefore, any two adjacent cogs on the loop must have different colors, otherwise the resulting gadget won't be working properly. If a cog in $$$S$$$ does not touch the loop, then it may have an arbitrary color.

How many different sets $$$S$$$ can Grigory choose to build a properly working gadget? Since the answer can be very large, find the value modulo $$$10^9 + 7$$$.

A minimum binary heap, often simply referred to as a "min-heap," is a specialized type of binary tree-based data structure used in computer science. It is a binary tree that has two main properties:

1. Heap Property: In a min-heap, for any given node, the value of that node is less than or equal to the values of its child nodes. This means that the minimum value in the heap is always found at the root node. In other words, the smallest element in the heap is at the top.
2. Binary Tree Structure: A min-heap is typically a complete binary tree, which means that all levels of the tree are fully filled except possibly for the last level, which is filled from left to right. This structural property allows min-heaps to be efficiently implemented using arrays.

Min-heaps are often used to implement priority queues, which are data structures that maintain a collection of elements with associated priorities. By keeping the minimum element at the root, min-heaps can quickly retrieve and remove the element with the highest priority (lowest value) in logarithmic time. However, removing any other element from a min-heap may need linear time.

Hank recently learned min-heaps. He wonders how many nodes can keep the $$$k$$$-th smallest element in a min-heap of $$$n$$$-nodes. Please write a program to help him.

You run a restaurant called Taste Of Pacific Cuisine (TOPC). This weekend, you will be hosting a large banquet that caters a sizable group of guests. Your chef designed $$$n$$$ types of dishes. To ensure every guest a chance to taste each type of the dishes, you plan to prepare two dishes per dish type. (Hence there are a total of $$$2n$$$ dishes at the banquet.)

There is a very long table in your restaurant, and you plan to exhibit all $$$2n$$$ dishes in a line on this table all at once. Not surprisingly, the length of the table fits exactly $$$2n$$$ dishes. As a considerate host, you plan to make sure that no two dishes of the same type are laying on the table together — this allows a variety of choices for introversion individuals who prefer not to wander around.

Now, some dishes have already been brought to the table. Can you quickly count the number of ways to place the remaining dishes such that no two dishes of the same type are placing together? You must compute this number quickly so you can give an introductory overview to your kitchen staff on how to place the remaining dishes — that's what you call an intro version. Since the number of ways could be large, it suffices to output the answer modulo $$$10^9+7$$$.

Jerry has earned acclaim as a renowned coach in the highly competitive realm of the International Collegiate Programming Contest (ICPC). His coaching prowess is exemplified by his unique approach — meticulously training his students to excel in ICPC competitions by harnessing the power of Java, a programming language seldom utilized in this arena. Consequently, Jerry's teams have become synonymous with excellence and are affectionately known as the "Java Warriors."

Jerry coaches $$$n$$$ teams to compete in the 2023 ICPC Taoyuan Regional Contest. The registration fee is $$$4000$$$ dollars per team, and Jerry does not have enough funds to pay for all Java Warriors. Jerry, facing a financial challenge in coaching multiple teams for the 2023 ICPC Taoyuan Regional Contest, prays to God with a heartfelt and sincere prayer.

"Dear God,

I come before you today with a humble heart and a deep desire to help my teams compete in the international collegiate programming contest. The registration fee is a significant hurdle, and I find myself lacking the funds needed to support them all.

I pray for your guidance and assistance, not only for myself but for the talented students who have put their trust in me as their coach. Please provide us with the resources necessary to cover the registration fees for these teams.

I understand that this contest is not just about winning but about fostering learning, teamwork, and growth in these young minds. Help us to overcome this financial obstacle so that we can continue to nurture their skills and aspirations.

I also pray for the wisdom to make the best decisions and the determination to explore all available options to secure the funds needed. If it is your will, open doors for us, connect us with individuals or organizations willing to support our cause, or inspire creative solutions to meet our financial needs.

Thank you, God, for hearing my prayer and for being a source of strength and guidance. I place my trust in you, knowing that with your help, we can overcome this challenge.

In your holy and gracious name, I pray,

Amen."

Upon hearing his heartfelt prayer, deeply moved by his sincerity and dedication, you are inspired to extend your support by covering the registration fees for the Java Warriors. Now, the question arises: how much should you donate to enable Jerry's teams to compete in the 2023 ICPC Taoyuan Regional Contest?

You are given a string $$$s$$$ consisting of lowercase English letters. A "kick" is defined as a substring of $$$s$$$ that starts with the letter 'k' followed by the letter 'i' followed by the letter 'c' followed by the letter 'k'.

Your task is to count the number of distinct "kicks" in the string $$$s$$$. Note that the kicks can overlap.

The concept of "location, location, location" is a common phrase used in real estate and business to emphasize the importance of the physical location of a property or business. In real estate, it suggests that the desirability and value of a property are heavily influenced by its location, often more so than by the property's features or condition. In business, it highlights that the success of a retail store or commercial establishment can be significantly impacted by its geographical location.

In recent years, people tend to buy electric vehicles, but the buyers soon find it is hard to install charging piles in their apartments or houses. Building a charging station can be a good idea to make a lot of money. Your boss, Lena, ask you to find a good location for establishing her charge station to serve the electric vehicle owners.

In recent times, there has been a growing trend towards the adoption of electric vehicles (EVs). However, many EV owners face the challenge of installing charging infrastructure in their apartments or houses. Establishing a charging station presents a lucrative opportunity in response to this demand. Your boss, Lena, has tasked you with identifying an optimal location for building a charging station to cater to the needs of electric vehicle owners.

You are given a list of $$$n$$$ locations represented as $$$(x, y)$$$ coordinates in a 2D plane. For each location, there is an apartment or a house without any charging infrastructure. Your task is to build a charging station at the location that is closest to all $$$n$$$ locations on the list. In this problem, distance is measured using the Manhattan distance metric. The Manhattan distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as $$$|x_1 - x_2| + |y_1 - y_2|$$$. Your goal is to find a location $$$(x, y)$$$ such that the sum of the Manhattan distances from that location to all $$$n$$$ locations on the list is minimized.