Lots of bubble tea shops are opening in Ann Arbor! You are the owner of the most recently opened downtown bubble tea shop. Since it is too competitive for most tea shops to survive, you have decided to promote your brand by offering a free cup of bubble tea to every $$$k$$$-th customer on each day.

For example, if $$$k = 10$$$ and on day $$$1$$$ you got $$$14$$$ customers and on day $$$2$$$ you got $$$33$$$ customers, then you gave away $$$4$$$ free cups: the 10th customer on day 1 and the 10th, 20th, and the 30th customers on day 2 each get one free cup.

You want to make sure that at least one customer gets a free drink each day. Write a program that given a log of visiting customers on the first $$$D$$$ days, validates that on each day someone got a free drink, or, If not, outputs the first day that, sadly, no customer gets a free drink.

Bois Blanc is the French name for a special type of basswood. But if you are an expert on Michigan geography, you know that it is also a Michigan island at the northern end of Lake Huron. Of course, there are lots of basswood trees on the island. Unlike its famous and historical neighboring island – Mackinac Island – there are very few residents and visitors on Bois Blanc Island. It is known primarily for its lighthouses, which help guide ships entering and leaving the Mackinac Straits connecting Lake Huron and Lake Michigan.

Let us suppose that Bois Blanc is perfectly circular (it's not, but it's difficult to come up with a problem for the real Bois Blanc shape). Designate a Cartesian coordinate system where the origin $$$(0,0)$$$ is at the center of the island and the island has radius 1. The State of Michigan has decided to build $$$N$$$ state-of-the-art lighthouses on the island, numbered $$$1,2,\ldots , N$$$. Lighthouse $$$i$$$ will be located at $$$(x_i, y_i)$$$ and have a specific light angle $$$\alpha_i$$$ and an angle of vision $$$\theta_i$$$ (see figure). Thus, the lighthouse illuminates the area between two rays, the first extending from $$$(x_i,y_i)$$$ at angle $$$\alpha_i-\theta_i/2$$$ and the second extending from $$$(x_i,y_i)$$$ at angle $$$\alpha_i+\theta_i/2$$$.

You have just been appointed Michigan Lighthouse Commissioner (congratulations!). You would like to ensure that these lighthouses altogether light up the entire periphery of the island (if all the lights are on) so that ships do not run ashore on the island. Island periphery is the circumference of the island. You are tasked to write a program that certifies this for you.

Exotic Canton, home to shopping plazas and stores... many, many stores. Especially large furniture stores. You are a manager of one these large furniture stores (one that sells just furniture, no meatballs). It is time for you to design a new "in-store shopping route" for your customers. The entire store can be represented by an $$$N\times M$$$ grid of square blocks. Each block is a $$$20$$$ foot by $$$20$$$ foot square space featuring one special type of furniture. You have come up with several design plans. In each of the plans, there is a "suggested walking direction" in every block pointing to one of the four neighboring blocks. We will use characters 'N', 'S', 'E', and 'W' for each of the four directions north, south, east, west.

A customer entering your store is supposed to pick an arbitrary block, then start following the suggested directions from block to block. Unfortunately, it may sometimes happen that the customer is not able to exit the store by doing this. Please count the number of blocks such that a customer starting from that block and following the suggested walking directions will never exit the store.

A cool thing about Detroit is that it is one of the few places where it is possible to go from the US to Canada by traveling south. You and $$$K$$$ of your Detroit friends have made plans to meet in Detroit at the Ambassador Bridge and cross the border to Windsor, in Canada, to have a dim sum lunch. You will each be traveling from some location in Detroit to the Ambassador Bridge. The road layout in Detroit is very complicated so for this problem we will describe a (fictional) layout by specifying a directed graph with N vertices (or junctions) and M directed edges (or one-way roads). You and your $$$K$$$ friends live at $$$K+1$$$ different junctions in the city. The junctions are numbered from $$$1$$$ to $$$N$$$. Junction $$$1$$$ is the Ambassador Bridge, and you and your friends live at the junctions numbered from $$$2$$$ to $$$K+2$$$.

You and your friends want to use as few roads as possible. Therefore, your task is to design a transportation plan for you and your friends to travel to the Ambassador Bridge that minimizes the number of roads used. That is, you want to find the minimal number of edges you would need so that it is possible to go from each of the junctions $$$2, \ldots, K+2$$$ to junction $$$1$$$ using just those edges.

East Lansing is home to MSU, one of the Michigan Wolverines' greatest rivals (we dare not speak the name Ohio State). Every year at the Michigan-MSU football game, stadium bleachers fill with fans clad in either green t-shirts (one of the MSU colors), or blue t-shirts (one of the Michigan colors), or some other neutral color (why are these people here, anyway?). As you stand on the field staring up an $$$N\times M$$$ grid of seats, you notice that there are some connected regions of green clad fans, some connected regions of blue clad fans, and a few neutrally clad fans interspersed.

You see an opportunity to promote your newly acquired t-shirt company. You decide to "suggest" to some of the neutrally clad people that they commit: you will provide a green or blue t-shirt for them to wear, but you choose the color each person gets. They all agree to wear the shirt you provide because, after all, who doesn't want a free t-shirt? You decide to choose the colors in such a way that the number of connected regions (i.e., the number of green regions plus the number of blue regions) is minimized. You believe this will be a more pleasing arrangement in the advertising photo you plan to take. To clarify: if you can find a way to go from a seat to an adjacent seat in one of the four directions (up, down, right, or left) without changing the color, then these two seats are considered to be in the same connected region; you do not consider diagonally adjacent seats of the same color.

You were assuming Flint, Michigan. Fooled you! This problem is about a middle school teacher named Mr. Flint. One day, Mr. Flint created a new number theory game for his students. He prepared a set of $$$N$$$ integers. Then, Mr. Flint asked the students, one-by-one, to choose a non-empty subset of those integers and compute the greatest common divisor of that subset. If the value is $$$1$$$, then the subset is called a "comprehensive" subset and the student receives a point. Students may not choose a previously chosen subset.

To make sure that every student has an opportunity to receive a point, Mr. Flint comes to you, because you were his favorite student years ago and he has heard that you are good at computing. He asks you to compute the number of comprehensive subsets. He hopes this number is at least the size of the class.

Feeding rabbits is never an easy job, especially when the rabbits are large. In the city of Grand Rabbits there are $$$N$$$ families of large rabbits that live along a long, straight street.

These families are numbered $$$1,2,\ldots ,N$$$ as you traverse the street. You run a carrot delivery company that delivers carrots to the rabbit families each day. Whenever you deliver to the $$$i$$$-th family on the street, you leave an order of $$$a_i$$$ pounds of carrots. You have worked out a schedule where you deliver on $$$D$$$ consecutive days. On the $$$d$$$-th day of the schedule, you deliver to the families numbered from $$$L_d$$$ to $$$R_d$$$, where $$$1 \le L_d \le R_d\le N$$$. Also on the $$$d$$$-th day of your schedule, you have $$$k_d$$$ trucks available to deliver these orders. To save wear on your trucks each day, you would like to apportion the $$$R_d - L_d + 1$$$ orders among the $$$k_d$$$ trucks so that the maximum load is minimized. Furthermore, to save gas, each truck should deliver to a set of consecutively numbered families. For example, if there are $$$10$$$ families in all, with $$$a_i=i$$$ for $$$i=1,2, \ldots ,10$$$, and on a particular day $$$d$$$, $$$L_d=1$$$, $$$R_d=6$$$ and $$$k_d=3$$$, then the first truck could deliver orders to families $$$1$$$, $$$2$$$, $$$3$$$, the second truck to families $$$4$$$,$$$5$$$, and the third truck to family $$$6$$$. The second truck has the maximum load, $$$9$$$ pounds, and this is minimal among all ways of apportioning the orders.

You are a manager of a beautiful but tiny take-out-only restaurant in Holland, a scenic city in western Michigan. All of your customers are regulars and you know that there will be $$$N$$$ customers planning to order food from your restaurant today. You even know the arrival time of each customer, the food that customer will order, and the tip that customer will leave. (You have studied data science so you can predict these things perfectly!) The restaurant service works as follows. When a customer arrives at the front door, they will enter a waiting queue. Your restaurant always serves the customer at the front of the queue. After this customer gets their food they will leave the restaurant immediately and then you are able to serve the next customer. However, due to social distancing limitations these days, your restaurant can hold at most $$$K$$$ customers at one time so you set this as the maximum queue size. Whenever a customer arrives at your restaurant and finds a full queue, that customer flies into a rage and leaves immediately. (If the queue is completely full with $$$K$$$ customers and the customer at the front of the queue is served at exactly the same time that a $$$(K+1)$$$st customer arrives to join the queue, there is no problem: the served customer at the front will exit and the arriving customer will join the queue simultaneously – rage avoided.)

As an awesome manager, you would like to avoid the potential frustration from these customers. To do so, you would select a subset of customers and tell them not to order food today, so that all the remaining customers can be served. As a clever manager, you would like to maximize the total amount of tips you get from the remaining customers.

Isle Royale is the only national park in Michigan. Since Isle Royale is a large island located very far north in Lake Superior, people rarely visit during the winter, and the wildlife and natural scenery are quite well preserved. The only access to the island is by a ferry that runs once a day. You have decided to write a video game about an adventure on Isle Royale. The map of the island is modeled as a graph with $$$N$$$ recreation sites (vertices) and $$$M$$$ paths connecting these sites (undirected edges).

In this game, a hero (the main character) begins at the entrance, recreation site $$$1$$$, where the ferry docks. Her objective is to travel along the paths to the campground at site $$$N$$$. Easy, right? But there are moose on the island! And a charging moose is three-quarters of a ton of dumb, terrifying fury. In fact, there is one moose at each recreation site $$$i$$$, where $$$1\le i\le N-1$$$.

Now there are two ways to deal with a moose (in the game – don't do this in real life): either stand perfectly still or climb a tree. The advantage of standing still is that it conserves energy, (but the moose does not leave). The advantage of climbing a tree is that the moose becomes frustrated and fades back into the forest, never to return, and the hero can advance. At each recreation site $$$i$$$, there is one tree and the hero must expend a certain amount of energy, $$$P_i$$$, to climb that tree. The hero begins the game with $$$E$$$ energy units, which you may assume is positive. Whenever the hero is at a recreation site $$$i\le N-1$$$, she may spend one minute executing one of the three following actions:

• Stand still. If her energy when she arrives at $$$i$$$ is less than $$$E$$$, she recovers one energy unit.
• Climb a tree. This costs her $$$P_i$$$ energy units.
• Move along a path to another recreation site $$$j$$$. This option is available only when the moose has left. Also, the hero loses $$$D_{i, j}$$$ energy units walking along the path.

Our hero may never have a negative amount of energy, even when she reaches the destination site $$$N$$$. As the game designer, you would like to ensure that the game is difficult but fun. Can you write a program that calculates the shortest possible amount of time (in minutes) a hero needs to travel to site $$$N$$$?

Little Jackson is learning to spell! Recently he learned the word "michigan". He is very excited to find all the occurrences of "michigan" on the street, even if they are spread out and hidden in other words. For example, 'michigan' occurs twice in 'momichigan' (because you can eliminate the first two letters, or the 2nd and 3rd letters). You can check that it occurs three times in 'mimichiganmi'. One day, Little Jackson sees an electric newsboard on the street. There are N characters on this board, but due to bugs the screen sometimes goes blank just as he finishes his count.Little Jackson screams, "how can I check the michigans when the world is changing so fast?"

Take pity on Little Jackson. Write a program that checks Little Jackson's answer before the screen goes blank.