Beltrano recently became interested in slacklining. Slacklining is a balance sport on an elastic Ribbon stretched between two fixed points, which allows the practitioner to walk and do maneuvers over the tape. During vacations all Beltrano wants to do is to practice, and that is why he went to a friend's farm, where there is a plantation of eucalyptus trees.
The Plantation is very well organized. The eucalyptus trees are arranged in $$$N$$$ rows with $$$M$$$ trees in each. There is a space of one meter between each row and the trees in different rows are all perfectly aligned with a space of one meter between them.
Beltrano will setup the slackline using two trees. When setting the slackline Beltran doesn't want the distance between the two trees to be too small, since the best maneuvers require the tape to have at least $$$L$$$ meters. Also you cannot stretch it too much because it has a maximum length of $$$R$$$ meters. Note that to stretch the tape between the two chosen trees there can be no other tree in the line formed, otherwise it would not be possible to use the whole tape for the maneuvers.
Beltrano would like to know in how many different ways you can setup the slackline using trees from the farm. Two forms are considered different if at least one of the trees where the tape was tied is different.
The input consists of a single line containing four integers, $$$N, M, L, R$$$, representing respectively the number of rows and columns of the plantation and the minimum and maximum lengths of slackline ($$$1 \leq N, M \leq 10^5$$$; $$$1 \leq L, R \leq 10^5$$$).
Your program should produce a single line with an integer representing in how many different ways the slackline can be set. As the result can be large, the answer must be module $$$10^9 + 7$$$.
2 2 1 1
4
2 3 1 4
13
1 2 1 1
1
Using marbles as a currency didn't go so well in Cubicônia. In an attempt to make it up to his friends after stealing their marbles, the Emperor decided to invite them to a game night in his palace.
Of course, the game uses marbles, since the Emperor needs to find some use for so many of them. $$$N$$$ marbles are scattered in a board whose lines are numbered from $$$0$$$ through $$$L$$$ and the columns numbered from $$$0$$$ through $$$C$$$. Players alternate turns. In his turn, a player must choose one of the marbles and move it. The first player to move a marble to position $$$(0, 0)$$$ is the winner. The movements are limited so the game could be more interesting; otherwise, the first player could just move a marble to position $$$(0, 0)$$$ and win. A movement consists in choosing an integer $$$u$$$ greater than $$$0$$$ and a ball, whose location is denoted by $$$(l, c)$$$, and move it to one of the following positions, as long as it is inside the board:
- $$$(l - u, c)$$$ or;
- $$$(l, c - u)$$$ or;
- $$$(l - u, c - u)$$$.
Note that more than one marble can occupy the same position on the board.
As the Emperor doesn't like to lose, you should help him determine which games he should attend. Also, as expected, the Emperor always take the first turn when playing. Assuming both players act optimally, you are given the initial distribution of the marbles, and should find if it is possible for the Emperor to win if he chooses to play.
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 1000$$$). Each of the following $$$N$$$ rows contains two integers $$$l_i$$$ and $$$c_i$$$ indicating on which row and column the $$$i$$$-th marble is in ($$$1 \leq l_i, c_i \leq 100$$$).
Your program should print a single line containing the character Y if it is possible for the Emperor to win the game or N otherwise.
2
1 3
2 3
Y
1
1 2
N
Grandpa Giuseppe won a professional pizza cutter, the kind of type reel and, to celebrate, baked a rectangle pizza to his grandchildren! He always sliced his pizzas into pieces by making cuts over continuous lines, not necessarily rectilinear, of two types: some begin at the left edge of the pizza, follow continuously to the right and end up in the right edge; other start on lower edge, follow continuously up and end up on the top edge. But Grandpa Giuseppe always followed a property: two cuts of the same type would never intersect. Here is an example with 4 cuts, two of each type, in the left part of the figure, which divide the pizza in 9 pieces.
It turns out that Grandpa Giuseppe simply loves geometry, topology, combinatorics and stuff; so, he decided to show to his grandchildren who could get more pieces with the same number of cuts if cross cuts of the same type were allowed. The right part of the figure shows, for example, that if the two cuts of the type that go from left to right could intercept, the pizza would be divided into 10 pieces.
Grandpa Giuseppe ruled out the property, but will not make random cuts. In addition to being one of the two types, they will comply with the following restrictions:
- Two cuts have at most one intersection point and, if they have, it is because the cuts cross each other at that point;
- Three cuts do not intersect in a single point;
- Two cuts do not intersect at the border of the pizza;
- A cut does not intercept a pizza corner.
Given the start and end points of each cut, your program should compute the number of resulting pieces from the cuts of Grandfather Giuseppe.
The first line of the input contains two integers $$$X$$$ and $$$Y$$$, ($$$1 \leq X, Y \leq 10^9$$$), representing the coordinates $$$(X, Y)$$$ of the upper-right corner of the pizza. The lower left corner has always coordinates $$$(0, 0)$$$. The second line contains two integers $$$H$$$ and $$$V$$$, ($$$1 \leq H, V \leq 10^5$$$), indicating, respectively, the number of cuts ranging from left to right and the number of cuts ranging from bottom to top. Each of the following lines $$$H$$$ contains two integers $$$Y_1$$$ and $$$Y_2$$$, a cut that intercepts the left side with y-coordinate $$$Y_1$$$ and the right side at y-coordinate $$$Y_2$$$. Each of the following $$$V$$$ lines contains two integers $$$X_1$$$ and $$$X_2$$$, a cut that intercept the bottom side at x-coordinate $$$X_1$$$ and the upper side at x-coordinate $$$X_2$$$.
3 4
3 2
1 2
2 1
3 3
1 1
2 2
13
5 5
3 3
2 1
3 2
1 3
3 4
4 3
2 2
19
10000 10000
1 2
321 3455
10 2347
543 8765
6
On the stage of an auditorium program there are three closed doors: door 1, door 2 and door 3. Behind one of these doors there is a car and behind the other two doors there is a goat. The production of the program randomly chooses the door where the car is without cheating. Only the host of the program knows where the car is. He asks the player to choose one of the doors. We can see that, because there is only one car, and at at least one of the two doors that the player did not choose, there has to be a goat!
Therefore, the presenter can always do the following: between the two doors that the Player did not choose, he opens one that has a goat, so that the player and the spectators can see the goat. The presenter now asks: "Do you want to change your door to the other door that is still closed?". Is it a beneficial change or not? The player wants to stay with the door that has the car, of course!
Paulinho saw a rigorous demonstration that the odds of the car being behind door the player chose initially is $$$\frac{1}{3}$$$ and the odds of the car being behind the other door which is still closed and the player did not choose initially is $$$\frac{2}{3}$$$ and therefore the exchange is advantageous. Paulinho doesn't conform, his intuition tells him that either way, the probability is $$$\frac{1}{2}$$$ for both doors still closed.
To bring this matter to an end, let's simulate this game thousands of times and count how many times the player won the car. We will assume that:
- The player picks door 1 initially;
- The player always changes doors after the presenter reveals a goat by opening one of the two doors that were not initially selected.
In these conditions, in a game, given the number of the door that contains the car, we can know exactly whether the player will win the car or not.
The first line of the input contains an integer $$$N$$$ ($$$1 \leq N \leq 10^4$$$), indicating the number of games in the simulation. Each of the $$$N$$$ following rows contains an integer: 1, 2 or 3; representing the door number containing the car in that game.
Your program must produce a single line containing an integer representing the number of times the player won the car in this simulation, assuming that he always chooses the door 1 and always switch doors after the host reveals a goat by opening one of the two doors that were not initially selected.
5
1
3
2
2
1
3
1
1
0
15
3
2
3
1
1
3
3
2
2
1
2
3
2
1
1
10
Given an initial configuration, the World War II German encryption machine Enigma replaces each letter typed on the keyboard with some other letter. The replacement strategy was quite complex, but the machine had a vulnerability: a letter would never be replaced by itself! This vulnerability was exploited by Alan Turing, who worked in the cryptanalysis of Enigma during the war. His goal was to find the initial configuration of the machine using the assumption that the message contained a certain usual expression of communication, such as the word ARMADA, for example. These expressions were called cribs. If the message FDMLCRDMRALF was encrypted, for example, the process of testing the possible configurations of the machine would be simpler because the word ARMADA, if present in the encrypted message, could only be in two positions, illustrated in the table below with an arrow. The remaining five positions could not match the crib ARMADA because at least one letter in the crib, underlined in the table below, would match its correspondent in the encrypted message; as the machine would never replace a letter by itself, these five positions could be ignored in the tests.
In this problem your program should compute, given a ciphertext and a crib, the number of possible positions for the crib in the encrypted message.
The first line of the input contains the encrypted message, which is a sequence of at least one letter and a maximum of $$$10^4$$$ letters. The second line of the input contains the crib, which is a sequence of at least one letter and at most the same number of letters of the message. Only the $$$26$$$ uppercase English letters appear on message and in the crib.
Print a line containing an integer, indicating the number of possible starting positions for the crib in the encrypted message.
FDMLCRDMRALF
ARMADA
2
AAAAABABABABABABABABA
ABA
7
Music festivals should be fun, but some of them become so big that cause headache for the goers. The problem is that there are so many good attractions playing in so many stages that the simple task of choosing which shows to watch becomes too complex.
To help goers of such festivals, Fulano decided to create an app that, after evaluating the songs heard on the users' favorite streaming services, suggests which shows to watch so that there is no other combination of shows that is better according to the criteria described below:
- To enjoy the experience as much as possible it is important to watch each of the selected shows from start to end;
- Going to the festival and not seeing one of the stages is out of the question;
- To ensure that the selection of artists is compatible with the user, the app counts how many songs from each artist the user had previously listened to on streaming services. The total number of known songs from chosen artists should be the largest possible.
Unfortunately the beta version of app received criticism, because users were able to think of better selections than those suggested. Your task in this problem is to help Fulano and write a program that, given the descriptions of the shows happening in each stage, calculates the ideal list of artists to the user.
The displacement time between the stages is ignored; therefore, as long as there is no intersection between the time ranges of any two chosen shows, it is considered that it is possible to watch both of them. In particular, if a show ends exactly when another one begins, you can watch both of them.
The first line contains an integer $$$1 \leq N \leq 10$$$ representing the number of stages. The following $$$N$$$ lines describe the shows happening in each stage. The $$$i$$$-th of which consists of an integer $$$M_i \geq 1$$$, representing the number of shows scheduled for the $$$i$$$-th stage followed by $$$M_i$$$ show descriptions. Each show description contains 3 integers $$$i_j, f_j, o_j$$$ ($$$1 \leq i_j \lt f_j \leq 86400$$$; $$$1 \leq o_j \leq 1000$$$), representing respectively the start and end time of the show and the number of songs of the singer performing that were previously heard by the user. The sum of the $$$M_i$$$ shall not exceed 1000.
Your program must produce a single line with an integer representing the total number of songs previously heard from the chosen artist, or −1 if there is no valid solution.
3
4 1 10 100 20 30 90 40 50 95 80 100 90
1 40 50 13
2 9 29 231 30 40 525
859
3
2 13 17 99 18 19 99
2 13 14 99 15 20 99
2 13 15 99 18 20 99
-1
After the end of the truck drivers' strike, you and the rest of Nlogônia logistics specialists now have the task of planning the refueling of the gas stations in the city. For this, we collected information on stocks of $$$R$$$ refineries and about the demands of $$$P$$$ gas stations. In addition, there are contractual restrictions that some refineries cannot supply some gas stations; When a refinery can provide a station, the shorter route to transport fuel from one place to another is known.
The experts' task is to minimize the time all stations are supplied, satisfying their demands. The refineries have a sufficiently large amount of trucks, so that you can assume that each truck will need to make only one trip from a refinery to a gas station. The capacity of each truck is greater than the demand of any gas station, but it may be necessary to use more than one refinery.
The first line of the input contains three integers $$$P, R, C$$$, respectively the number of gas stations, the number of refineries and the number of pairs of refineries and gas stations whose time will be given ($$$1 \leq P, R \leq 1000$$$; $$$1 \leq C \leq 20000$$$). The second line contains $$$P$$$ integers $$$D_i$$$ ($$$1 \leq D_i \leq 10^4$$$), representing the demands in liters of gasoline of the gas stations $$$i = 1, 2, \dots, P$$$, in that order. The third line contains $$$R$$$ integers $$$E_i$$$ ($$$1 \leq E_i \leq 10^4$$$), representing stocks, in liters of gasoline, of refineries $$$i = 1, 2, \dots, R$$$, in that order. Finally, the latest $$$C$$$ lines describe course times, in minutes, between stations and refineries. Each of these rows contains three integers, $$$I, J, T$$$ ($$$1 \leq I \leq P$$$; $$$1 \leq J \leq R$$$; $$$1 \leq T \leq 10^6$$$), where $$$I$$$ is the ID of a post, $$$J$$$ is the ID of a refinery and $$$T$$$ is the time in the course of a refinery truck $$$J$$$ to $$$I$$$. No pair $$$(J, I)$$$ repeats. Not all pairs are informed; If a pair is not informed, contractual restrictions prevents the refinery from supplying the station.
Print an integer that indicates the minimum time in minutes for all stations to be completely filled up. If this is not possible, print −1.
3 2 5
20 10 10
30 20
1 1 2
2 1 1
2 2 3
3 1 4
3 2 5
4
3 2 5
20 10 10
25 30
1 1 3
2 1 1
2 2 4
3 1 2
3 2 5
5
4 3 9
10 10 10 20
10 15 30
1 1 1
1 2 1
2 1 3
2 2 2
3 1 10
3 2 10
4 1 1
4 2 2
4 3 30
-1
1 2 2
40
30 10
1 1 100
1 2 200
200
The public transport system of Nlogônia has an express network connecting the main points of interest of the country. There are $$$N−1$$$ bullet trains connecting $$$N$$$ attractions such that from one of the points of interest you can reach any other using only this network.
As anywhere in the world, it is common that there is graffiti on the train stations. What caught the attention of the police of the country is the fact that in each one of the stations it is possible to find exactly one letter pinned with a specific style. The hypothesis is that criminals may be changing the graffiti as a means of communication and, therefore, it was decided to create a system capable of monitoring the graffiti and its amendments.
Given a pattern $$$P$$$, the description of the connections between stations and the suspicious letters in each of them, your task is to write a program able to deal with the following operations:
- 1 $$$u$$$ $$$v$$$: print how many times the pattern $$$P$$$ occurs in the path from $$$u$$$ to $$$v$$$ if we look at the string of characters associated with the consecutive vertices of the path;
- 2 $$$u$$$ $$$x$$$: change the suspicious letter at the station $$$u$$$ to $$$x$$$.
The first input line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$), representing the number of stations and the number of transactions that must be processed. The second line contains the pattern $$$P$$$ monitored ($$$1 \leq |P| \leq 100$$$). The third line contains a string with $$$N$$$ characters representing the letters initially associated with each of the stations. Each of the following $$$N−1$$$ lines contains two integers $$$u$$$ and $$$v$$$ indicating that there is a bullet train between $$$u$$$ and $$$v$$$. The following $$$Q$$$ lines describe the operations that must be processed as described above.
Your program should print a line for each operation of type 1 containing an integer that represents the number of occurrences of the pattern $$$P$$$ on the way.
4 4
xtc
xtzy
1 2
2 3
3 4
1 1 3
2 3 c
1 1 3
1 3 1
0
1
0
6 7
lol
dlorlx
1 2
1 3
3 4
3 5
5 6
1 2 6
2 3 l
2 6 l
2 5 o
1 2 6
2 1 o
1 6 2
0
1
2
5 2
aba
ababa
1 2
2 3
3 4
4 5
1 1 5
1 5 1
2
2
In the control panel of an enormous amphitheatre, there are $$$N$$$ switches, numbered from 1 to $$$N$$$, that control the $$$M$$$ light bulbs of the place, which are numbered from 1 to $$$M$$$. Note that the number of switches and light bulbs is not necessarily the same and this happens because each switch is associated not to a single light bulb, but to a set of light bulbs. When a switch is activated, each one of the bulbs associated to it is toggled. If the bulb is lit, then it will be switched off, otherwise it will be switched on.
Some bulbs are lit initially and the janitor in charge of the amphitheatre has to switch off all them. He started trying to press the switches randomly, but as soon as he figured out that it wouldn't necessarily work, he decided to follow a fixed strategy. He will trigger the switches $$$1, 2, 3, \dots, N, 1, 2, 3, \dots$$$ in other words, every time after triggering the switch number $$$N$$$, he resumes the procedure from the switch number 1. He intends to keep pressing switches by the given strategy until all bulbs are switched off at the same time (in that moment he stops pressing the switches). Will his strategy work?
Given the bulbs which are initially lit and the sets of lamps associated to each switch, your program should compute the number of times the janitor will press switches. If by following the given strategy the janitor is never able to switch off all the lamps at the same time, your program should print -1.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 1000$$$) representing, respectively, the number of switches and the number of light bulbs. The second line contains an integer $$$L$$$ ($$$1 \leq L \leq M$$$) followed by distinct integers $$$X_i$$$ ($$$1 \leq X_i \leq M$$$), representing the bulbs that are lit in the first place. Each of the following $$$N$$$ rows contains an integer $$$K_i$$$ ($$$1 \leq K_i \leq M$$$) followed by $$$K_i$$$ distinct integers $$$Y_i$$$ ($$$1 \leq Y_i \leq M$$$), representing the bulbs attached to switch $$$i$$$ ($$$1 \leq i \leq N$$$).
Your program must print a single line containing an integer representing the number of times the janitor will press the switches by following the strategy described, until all the lights were off at the same time. If that never happens, print -1.
6 3
2 1 3
3 1 2 3
2 1 3
2 1 2
2 2 3
1 2
3 1 2 3
5
3 3
2 2 3
1 3
2 1 2
1 2
-1
A far far away kingdom has $$$N$$$ cities, among which $$$K$$$ are capitals. King Richard wants to build transmission lines, each one directly connecting two cities. Also, there needs to be a path, i.e. a sequence of transmission lines, between any pair of capitals.
Each transmission line has an associated cost, which is the Euclidean distance between the two cities that the transmission line connects. As the king is greedy, he wishes that the transmission lines are set up so that the total cost (sum of the costs for each line) is kept as small as possible.
The figure A shows an example of a kingdom with $$$N = 10$$$ cities and $$$K = 4$$$ capitals. The Chief Engineer reported to the king the solution shown in figure B. Such solution, in fact, minimizes the total cost. But the king didn't like to see a capital with more than one transmission line. He then determined a new restriction: a capital can be connected to only one other city. That way, after working a lot, Chief Engineer presented the new solution, illustrated in figure C. He's just not so sure if this is the optimal solution, so he needs your help.
Given the coordinates of the cities, your program should compute the smallest total cost to build transmission lines so that every pair of capitals is connected by a sequence of transmission lines and every capital is directly connected to only one city.
The first line of the input contains two integers $$$N, K$$$ ($$$4 \leq N \leq 100$$$; $$$3 \leq K \lt \min(10, N))$$$, indicating respectively the number of cities and the number of capitals. The following $$$N$$$ lines contain two integers $$$X$$$ and $$$Y$$$ each ($$$−1000 \leq X, Y \leq 1000$$$), representing the coordinates of a city. The $$$K$$$ first cities are the capitals. There are no two cities with the same coordinates.
Print a line containing a real number, with 5 decimal places, indicating the smallest total cost to build transmission lines, according to the restrictions above.
6 4
-20 10
-20 -10
20 10
20 -10
-10 0
10 0
76.56854
22 9
-3 -25
0 -6
-1 -9
2 -21
-5 -19
0 -23
-2 24
-4 37
-3 33
-3 -12
2 39
3 -49
-3 -26
2 24
5 3
-4 -9
-2 -9
-4 8
3 -33
-2 31
-1 -13
0 2
95.09318
In this strange planetary system that can be represented in a Cartesian plane, $$$N$$$ planets orbit circularly around a star at coordinates $$$(0, 0)$$$. The star is strictly contained within all circles that define the orbits, but the center of each orbit is not necessarily at coordinates $$$(0, 0)$$$. The circular orbits are in any position such that if two orbits intersect, then they intersect in two distinct points. In addition, three orbits do not intersect at a common point.
Scientist John Kepler is interested in testing a new theory and asked for your help to compute the number of intersection points between the orbits, if that number is less than or equal to $$$2N$$$. Otherwise, we just need to know that the number is greater than $$$2N$$$.
The first line of the input contains an integer $$$N$$$ ($$$2 \leq N \leq 150000$$$), representing the number of orbits. Each of the following $$$N$$$ rows contains three real numbers with exactly 3 decimal digits, $$$X, Y$$$ ($$$−25.0 \leq X, Y \leq 25.0$$$) and $$$R$$$ ($$$1.0 \leq R \leq 200000.0$$$), the coordinates of the center and the radius of the orbit, respectively.
Print a line containing an integer, representing the number of points of intersection between the orbits, if that number is less than or equal to $$$2N$$$. Otherwise, print greater.
6
0.000 1.000 4.000
0.000 0.000 10.500
4.000 0.000 6.000
1.000 1.000 1.750
-1.000 -1.000 8.000
2.000 -2.000 4.000
10
4
-1.000 -1.000 3.000
1.000 -1.000 3.001
-3.004 3.003 5.002
1.000 1.000 3.005
greater
The subway system of a major city is formed by a set of stations and tunnels that connect some pairs of stations. The system was designed so that there is exactly one sequence of tunnels linking any pair of stations. The stations for which there is only one tunnel passing through are called terminals. There are several train lines that make round trips between pairs of terminal stations, passing only through the stations in the unique path between them. People are complaining about the current lines. Therefore, the mayor ordered that the lines are redefined from scratch. As the system has many stations, we need to help the engineers, who are trying to decide which pair of terminals will define a line.
The figure illustrates a system where terminal stations are shown as filled circles and the non-terminals are shown as empty circles. On the leftmost picture, if the pair $$$(A, B)$$$ define a line and the pair $$$(C, D)$$$ defines another, they won't have any common station. But, on the rightmost picture, we can see that if the pairs $$$(E, F)$$$ and $$$(G, H)$$$ are chosen, those two lines will have two stations in common.
Given the description of the system and a sequence of $$$Q$$$ queries consisting of two pairs of terminals, your program should compute, for each query, how many stations the two lines defined by those pairs have in common.
The first line of the input contains two integers $$$N$$$ ($$$5 \leq N \leq 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 20000$$$), representing respectively the number of stations and the number of queries. The stations are numbered from 1 to $$$N$$$. Each of the following $$$N−1$$$ lines contains two distinct integers $$$U$$$ and $$$V$$$ ($$$1 \leq U, V \leq N$$$), indicating that there is a tunnel between stations $$$U$$$ and $$$V$$$. Each of the following $$$Q$$$ lines contains four distinct integers $$$A, B, C, D$$$ ($$$1 \leq A, B, C, D \leq N$$$), representing a query: the two train lines are defined by pairs $$$(A, B)$$$ and $$$(C, D)$$$.
For each query, your program must print a line containing an integer representing how many stations the two train lines defined by the query would have in common.
5 1
1 5
2 5
5 3
5 4
1 2 3 4
1
10 4
1 4
4 5
3 4
3 2
7 3
6 7
7 8
10 8
8 9
6 10 2 5
1 9 5 10
9 10 2 1
5 10 2 9
0
4
0
3
The Boolean satisfiability problem (SAT) is to decide, given a Boolean formula in conjunctive normal form, if there is any assignment of values true or false to each variable so that the formula is true. In conjunctive normal form, the formula is given in a very specific format. Firstly, the only logical operations used are the "and", "or" and the negation, denoted by $$$\wedge$$$, $$$\vee$$$ and $$$\neg$$$, respectively. A formula is formed through operation "and" of different parts, denoted clauses, $$$C_1, \dots, C_m$$$. In this way, a formula will have the following format:
In addition, each of the clauses also has a specific format. In particular, each of the clauses is composed by the "or" of literals, which are variables or negations of variables surrounded by parenthesis. Thus $$$(x_1 \vee \neg x_2)$$$ is a valid clause, while $$$(x_1 \wedge \neg x_2)$$$ is not because of the operator "and". A complete example of formula would be:
A variation of SAT is known as $$$k$$$-SAT, where each clause has at most $$$k$$$ literals. The formula above would be an instance of the 3-SAT problem, but not 2-SAT. Note that, in all of these problems, for a formula to be true, each of the clauses must be true and, therefore, at least one of the literals (the form $$$x_i$$$ or $$$\neg x_i$$$) of each clause must be true.
An assignment is a way to set the variables as true or false. In this problem we are interested in a variation of the 3-SAT problem, in which a valid assignment must have exactly 1 or exactly 3 literals true in each clause. Given a formula, your task is to decide whether there is a valid allocation, taking into account such extra constraint. If there is a valid assignment, you must print the lexicographically largest one. The lexicographical order is defined as follows: given two different assignments, we can compare them by looking for the smaller variable index that differs on the two assignments; of the two assignments, the greater is the one that gives true value for this variable.
The first line of the input contains two integers $$$M$$$ and $$$N$$$ ($$$1 \leq M, N \leq 2000$$$), describing the number of clauses and variables, respectively. Then $$$M$$$ lines shall be provided, each describing a clause (see example for details of the format). Consecutive clauses are separated by the string and. Each clause contains at most 3 literals. The variables are denoted by x followed by a number between 1 and $$$N$$$. There will be no two consecutive spaces or spaces at the end of the lines. The first example describes the formula $$$\varphi$$$ defined right above.
Your program must print a single line containing $$$N$$$ characters corresponding to a valid assignment that is the lexicographically largest, or impossible if there is no valid assignment. The $$$i$$$-th character must be T if the variable is true on the assignment and F otherwise.
4 3
(x1 or x2 or x3) and
(not x1) and
(x1 or not x2 or x3) and
(x2 or not x3)
impossible
5 6
(not x1) and
(x1 or x2 or x4) and
(x1 or x3 or x5) and
(not x2 or x3 or x5) and
(x2 or x3 or not x4)
FTTFFT
1 1
(x1 or x1 or not x1)
F