A string is considered palindrome if it's the same if you read it from the left or from the right (if it stays the same when you reverse it).
In this problem you are given a string, and your task is to swap 2 characters at different positions to make the string palindrome (note that you must do this step exactly once).
The input contains just 1 line which is the string you are going to check, the string consists of at least 2 and at most 500,000 lower case English letters.
Print "YES" if you can make the given string palindrome by applying the above step exactly once, otherwise print "NO".
ab
NO
aba
YES
axax
YES
In the second test case, you can swap the first and last characters (which won't make any change), and the string will stay palindrome.
P.S. The judge is cute enough today and didn't allow strings with length 1.
Wet Shark is now trying to help Dry Shark cheat in a game so that Dry Shark can win. The game is played on a regular xy coordinate grid. There is a stack of n cards. Wet Shark will hand all n cards to Dry Shark, in some order. When Dry Shark receives a card, he must move in the direction stated by the card.
In the game, there are 2 types of cards, as follows:
Type 1 cards are in the form “Right X, Left Y.” This means that Wet Shark must move right X units and then move left Y units, in that order.
Type 2 cards are in the form “Up X, Down Y.” This means that Wet Shark must move up X units and then move down Y units, in that order.
Dry Shark initially starts on the point (1, 1). If Wet Shark ever crosses or lands on the x or y axis after he is handed any card, he becomes consumed by the Evil Sharks, and therefore loses the game. If Wet Shark can hand Dry Shark the cards in some order so that he never gets consumed by the Evil Sharks, Dry Shark wins the game.
Determine if there is a way Wet Shark can hand Dry Shark the cards so that Dry Shark can win the game.
The Evil Sharks, however, still want to eat Dry Shark in the game. Therefore, help the Evil Sharks determine what point Dry Shark will land on if he wins.
The first line contains an integer n (1 ≤ n ≤ 1000).
Each of the next n lines contains 3 space-separated integers ti, Xi, Yi (1 ≤ ti ≤ 2, - 1000 ≤ Xi, Yi ≤ 1000), representing the type and values written on the ith card. If ti = 1, a Type 1 card is depicted; X and Y are the units Dry Shark is to move right and left, respectively. If ti = 2, a Type 2 card is depicted; X and Y are the units Dry Shark is to move up and down, respectively.
On the first line of the output, output a single "YES" or "NO" (quotes for clarity). Output "YES" if Dry Shark can win and "NO" if Dry Shark cannot win.
If Dry Shark can win, output the coordinates of the point Wet Shark will be at after Wet Shark gives him all the cards. Check the sample output for the exact format.
5
1 4 1
1 2 7
2 4 9
2 5 6
2 3 4
NO
2
1 50 1
2 2 1
YES
(50, 2)
Note that the Xi, Yi could be negative. Going right - n blocks is equivalent to going left n blocks, and going up - m blocks is equivalent to going down m blocks.
Wet Shark has a function 
, which returns the sum of the squares of the digits of a number. For example, 
and 
.
Dry Shark is trying to fight many enemies. These enemies are strange, however, and each enemy is represented by a different positive integer, let's call it ID. Dry Shark has a function 
, which takes the ID of the enemy and returns the amount of power that enemy has. The body of the function is 
, which utilises the function that Wet Shark gave to him. Note that 
and 
Dry Shark is given a number n. For a number n, Dry Shark knows there could potentially be any enemy whose number has n digits in it. Formally, given an integer n, the enemies could be represented as any integer from 10n - 1 to 10n - 1, inclusive. For example, if n = 2, enemies could be represented by any integer from 10 to 99 inclusive.
Dry Shark wants to know four things:
1) The ID of any of the enemies with maximum power
2) The ID of any of the enemies with minimum power
3) The power of the enemies with maximum power
4) The power of the enemies with minimum power
The only line contains an integer n (1 ≤ n ≤ 2, 500, 000).
Output 4 lines, one integer on each line, representing the things Dry Shark wants to know.
The first line should state the ID of any of the enemies with maximum power.
The second line should state the ID of any of the enemies with minimum power.
The third line should state the power of the enemies with maximum power.
The fourth line should state the power of the enemies with minimum power.
If there are multiple solutions to any of Wet Shark's queries, you can output any of them.
1
1
9
0
-72
Problem note: 001 is not a valid 3-digit ID because it is not in the range 102 to 103 - 1. 0 is not a valid 1-digit ID for a similar reason.
Sample Test 1: We can tabulate GetPower(n) for all 1-digit IDs:
Therefore, the minimum is -72, the maximum is 0, and values 9 and 1, respectively, produce these.
Today, Wet Shark was given a list of non-necessarily distinct prime integers, a1, a2, ...an.
Wet Shark defines k as the smallest integer such that for 1 ≤ i ≤ n, k mod ai = ai - 1.
Wet Shark also has an additional integer, o. Tell Wet Shark whether or not k is divisible by o.
The first line contains one integer, n 1 ≤ n ≤ 100000.
The second line consists of n space separated integers, the list of primes. Each prime ranges from 2 to 100000.
The third line consists of the additional integer, o, ranging from 1 to 100000.
If k is divisible by o, output "YES". Else, output "NO".
1
3
2
YES
2
3 3
4
NO
Mike has a vacation of m days, and he's going to explore n cities numbered from 1 to n. He can start to visit on the first day any city. If on day d he visited city c1 then on the day d + 1 he can visit city c1 (stay where he's for one more day) or city c2 if there is a road between cities c1 and c2.
He can visit a city any number of times. There are k types of roads, each type is described using 3 integers ai, bi and ci, signifying that there are bidirectional roads between cities (ai and ci), (ai + 1 and ci) ... (bi and ci) note that there can be a road between a city and itself, it is also given the fact that ci ≠ cj (1 ≤ i < j ≤ k).
In day i (1 ≤ i ≤ m), if he visits city j (1 ≤ j ≤ n) he gets pleasure Pi, j.
Help him find the maximal sum of pleasure in all the days he can achieve.
The first line contains 3 integers n, m and k (1 ≤ n × m, k ≤ 300, 000).
The next m lines contains n integers separated by a space, representing matrix P (0 ≤ Pi, j ≤ 109).
The next k lines, each one contains 3 integers separated by a space, representing the different types of roads – ai, bi, ci (1 ≤ ai ≤ bi ≤ n, 1 ≤ ci ≤ n).
Output the maximal sum of pleasures he can achieve.
3 3 2
1 2 3
5 6 7
11 5 3
1 1 2
2 3 3
20