You've just discovered Odoo, an awesome suite of web-based open-source business apps. Not only impressed by the idea and quality of the apps, you, as a member of the open-source community, loved the fact that Odoo is open source.

After hours reading the codebase and learning how Odoo works, you decide to check the commit history of the most fun app: Real State! But wait... you just realized... there is a pattern in some of the author emails! Of course! Odoo employees! There is also a whole team of developers making sure the codebase is clean and developing new features!

You realized that Odoo emails have the format S@odoo.com, where S is a string of lowercase letters with size 2, 3 or 4. Really excited by your own discovery, you decide to write a script to check if an email is a potential Odoo email. That is, if it follows the described format.

It's party time at Odoo! These Odooers... they sure know how to party! However, as any mortal human being, they are having trouble setting up the printer for decorations.

The printer was supposed to print a nice big ODOO strip, but, instead, it printed a scrambled sequence of O's and D's, even with more letters than needed. For instance, it just now printed ODODODODODO...

The party organization committee is now going to fix the strip, making it a proper ODOO, but following the operations bellow:

• Removing a letter: Since it's a strip, they can only cut out a letter from the beginning or the end, not from the middle. They can't remove more than one letter at a time.
• Transforming a letter: O's and D's are quite similar, so they can transform an O into a D and vice-versa.

Being the clever bunch they are, the Odooers want to fix the strip as quickly as possible. How many minutes will it take them at the least? Both operations above have the same cost of 1 minute to be done.

We're trying to install $$$n$$$ Odoo modules from your local machine to the server.

Imagine that the path from your local machine to the server is a line where your machine is at position $$$0$$$ and the server is at position $$$k$$$ ($$$k = 10^{9}$$$, fixed).

Initially, each module has:

• An initial position between $$$0$$$ and $$$k-1$$$
• An initial capacity to resist viruses.

Each second, the module advances $$$1$$$ unit (its position advances by $$$1$$$).

You started the installation, and all your modules were moving to the server, but someone introduced $$$m$$$ viruses in different positions of the line in the opposite direction of the installation (right to left) (Viruses move with the same speed).

Each virus has different capacities to impact each module. It can have capacity $$$X$$$ against module $$$A$$$ and capacity $$$Y$$$ against module $$$B$$$.

When a module and a virus collide (touch each other at any part of the line):

• If the virus does not have any capacity against this specific module, nothing happens (the module continues its path to the server, and the virus continues its path to the left looking for a module to kill).
• If the virus does have capacity against this module, the one with lower capacity is removed. If the module survives, its capacity decreases by the virus capacity against it. Yes, you're right! If they both have the same capacity, they are both removed.

At Odoo, several tasks are processed daily on our dedicated servers. These tasks need to be inspected by a person who guarantees correct performance in all of them.

Natan is in charge this week, but he needs to finish all the tasks within the time limit set for him. However, to save more resources, Natan needs to find out the smallest amount of dedicated servers that will be needed to finish all tasks within the time limit or verify that this is impossible.

Each task takes a certain duration to perform. All the tasks need to be started in order (i.e., task $$$i$$$ just can start if task $$$i-1$$$ starts at the same time or at an earlier time).

Each dedicated server can only perform a maximum of one task at a time and it can start a new task as soon as it finishes the one it is currently doing.

As a new developer at Odoo, you were tasked with helping Natan solve this problem. Find out the smallest number of dedicated servers needed to perform these tasks or, if impossible, print the number -1.

Odoo has introduced its new POS Kiosk app, which allows restaurants to receive orders from clients in their shop and process them easily. So basically, there are 2 main functionalities of the POS kiosk: add order , mark order as done so it's removed from the screen.

For performance reasons, the updates in the database are made in batches. It means that for each batch of updates, there is only one query executed to remove/add records to the database.

To test the database performance, Odoo developers came up with the following process :

• There will be a randomly generated array of operations $$$A$$$ of size $$$n$$$ based on analytics of real data where $$$A_{i}$$$ is the difference between the created and deleted records of that batch of updates. For example, if $$$A_{i}=3$$$ , it means there are 3 more created records than deleted records in that batch of operations.
• Now for every integers $$$L$$$ to $$$R$$$ $$$(1 \leq L \leq R \leq n)$$$ they will calculate $$$f(A,L,R)$$$ which goes as follows, from $$$L$$$ to $$$R$$$, executes the queries one by one, and reports the maximum extra units of space needed from its initial state if we consider that each record needs $$$1$$$ unit of space. It means that if $$$A_{i} \gt 0$$$ we need extra $$$A_{i}$$$ units of space to be able to execute that query , otherwise we free $$$-A_{i}$$$ units of space from the database that can be filled later by some other updates. For example, for the sequence $$$2$$$ $$$3$$$ $$$-4$$$ $$$6$$$, the answer is $$$7$$$, and for $$$2$$$ $$$3$$$ $$$-4$$$ $$$3$$$, the answer is $$$5$$$.

Given the generated array $$$A$$$, can you simulate the experiment and find : $$$$$$\sum_{1\leq L \leq R\leq n}f(A,L,R)$$$$$$

There are $$$n$$$ employees at Odoo numbered from $$$1$$$ to $$$n$$$, each employee has exactly $$$1$$$ manager, except for the head with the number $$$1$$$ who has no manager. So they form a rooted tree.

We call employee $$$a$$$ a subordinate of another employee $$$b$$$ if either $$$b$$$ is the manager of $$$a$$$, or the manager of $$$a$$$ is a subordinate of employee $$$b$$$. In particular, subordinates of the head are all other employees of the company.

You will be given very sensitive information: An integer array $$$A$$$ of size $$$n$$$ where $$$A_i$$$ is the salary of the $$$i_{th}$$$ employee at Odoo $$$(1 \le i \le n)$$$.

For the following $$$q$$$ years, at the beginning of the year, one lucky employee $$$u$$$ is picked alongside an integer value denoted as $$$x$$$. For that employee, their salary will be multiplied by $$$x$$$. Also, for all subordinates of $$$u$$$ their salary will be multiplied by $$$x$$$ as well.

An employee is happy at some year if their salary was divisible by $$$k$$$ in that year. You will be given the value of $$$k$$$ and your goal is to print $$$n$$$ integers where the $$$i_{th}$$$ integer $$$(1 \leq i \leq n)$$$ is the first year at which employee number $$$i$$$ was happy.

If one employee was happy initially print $$$0$$$ and if they were never happy print $$$-1$$$.

In Odoo, we foster a large open-source community offering a plethora of apps, all accessible for free. Kinho dedicates himself to developing and enhancing select apps within this ecosystem. While each app boasts a wealth of features, let's simplify our focus to four key attributes:

• An App ID to uniquely identify each application.
• The ID of its parent app (Pid). Odoo operates with an inherent mode, enabling one app to inherit properties from another.
• A profit rate (PR), denoting the daily profit generated by the app.
• A bonus, representing a fixed profit received throughout the day upon installing the app.

To compute the profit for app $$$i$$$ on a specific day $$$d$$$, we use the following formula:

$$$$$$profit_{i} = PR_{i} * d + bonus_{i}$$$$$$

It's noteworthy that when Kinho develops a new app, its profit rate is strictly greater than its parent app. This is because the primary motive behind developing a new app is to enhance an existing one.

Now Kinho is curious, given an app and considering all the apps from which it inherits, what is the highest profit for app for a given day?

In the Odoo interface, you realize that it's all about views and smart buttons. Let's consider that Odoo has N distinct views and for each view, there are some smart buttons to take you to other views.

It's guaranteed that :

• From every view, you can go to any other view using a series of clicks on smart buttons.
• If there is a button that takes you from view $$$V_{1}$$$ to view $$$V_{2}$$$ , then there is a button that takes you from $$$V_{2}$$$ to $$$V_{1}$$$.
• There is only one way to go from any view to any other view using the minimum number of clicks. (the views construct a tree like structure).

Since views are a very important part of Odoo, they should be tested carefully. That's where the Odoo tour test comes into play. The developers at Odoo developed an automatic testing program which will run infinitely. The test consists of a cyclic list of views of size $$$k$$$ (not necessarily distinct). At the start, the program starts from a view at some position $$$p$$$ in the list, then he goes to the next view at position $$$p+1$$$ using the minimum number of clicks, then to the view at position $$$p+2$$$ and so on (the view at position $$$1$$$ comes after the view at position $$$k$$$). A view is called tested if it is visited at least one time at some point during the test. You realized that some views might not get tested, so you introduced some updates to the original list of views and some other queries to collect analytics. The queries go as follows:

• $$$1$$$ $$$p$$$ $$$u$$$: update the view at position $$$p$$$ by view with id $$$u$$$
• $$$2$$$ $$$p$$$ $$$u$$$: find the minimum number of clicks needed for the view with id $$$u$$$ to be tested for the first time if the program starts running from position $$$p$$$ , print $$$-1$$$ if it's impossible to test that view.