You will be surprised, but there are «Four in a Row» tournaments out there. Its rules are quite simple: two players play on a 7 × 9 field with 7 rows and 9 columns, which is placed vertically on the table. Players take turns dropping their colored chips into one of the nine columns, and the chip falls to the lowest unoccupied position in the column. When all seven chips are in a column, no more chips can be placed in that column, but a player can choose to skip a turn placing an imaginary chip in this column, that kind of move costs one chip. The game ends when one of the players creates a sequence of four chips of the same color in a column, row, or diagonal. The player who made the last move is declared the winner. If all 63 chips are used and none of the players has won, the game is either a draw if the entire field is filled, or an open end if there are still empty positions.
Professional «Four in a Row» players play very quickly, and to analyze the game afterwards, a scribe is present at each match, recording every move made by the players. It is clear that at any point in the game, there can be no more than nine possible moves, each of which is represented by the column number where the chip was dropped or where the turn was skipped. For convenience, the scribes write all the moves in one line.
In the final of the World Championship, the two greatest players of the generation, Parviz and Voropshe, compete. A novice bookmaker, Vadim, accepts bets only on the victory of one of the two players. If Parviz wins, who starts the game, Vadim will distribute all the money in proportion to those who bet on him. If Voropshe wins, Vadim will distribute the money to those who bet on him. In the event of a draw, Vadim keeps the entire bank. A professional game cannot end with an open end, as both players would be disqualified.
Unfortunately, Vadim overslept this match, and he needs to return the money. Or does he? Vadim found a record of the match made by the scribe, but it turned out to be very strange. Somehow, the scribe recorded in one line both the matches and the random moves of bored players. In order to make the right decision about the money, Vadim urgently needs to determine how many substrings in this line are records of one player’s victory and how many are records of draws. He is not interested in who won the match, as all the money will go to the original bettors in the event of a victory, and Vadim will make a good profit in the event of a draw. He is also not interested in games with open ends, as they could not have occurred in this match. Help Vadim, and maybe he will share a piece of cake or a slice of pie with you.
The input consists of a single line containing a string of length N consisting of digits from «1» to «9» without spaces — the record of all moves made by the scribe (1 ≤ N ≤ 104).
Output two integers separated by a space — the number of substrings in the given record that represent a victory for one of the players, and the number of substrings that represent a draw.
In the game «3435363», the first player wins by creating a sequence of 4 chips in the third column; in the game «4353637», the first player also wins by creating a sequence of 4 chips in the bottom row; no other substring represents a completed game.
Problem Author: Vadim Barinov
Problem Source: Ural School Programming Contest 2021