Natasha has several cats at home. It is known that during the night, one cat drops from $$$A$$$ to $$$B$$$ poorly secured items (Natasha has an infinite number of such items).

One night Natasha heard in her sleep something fall $$$N$$$ times. Determine the minimum number of cats she could have.

There are 2*N+1 empty cards in a row. Petya writes the sign ">" or "<" on each even card at his discretion. Will Vasya be able to write numbers from 1 to (N+1) on odd cards so that all inequalities are true? Each number must be written exactly once.

Regular expressions are a flexible way to define patterns for searching and replacing text. In this problem, we consider a subset of regular expressions that includes only:

1. Digits from 0 to 9
2. Parentheses
3. The symbol '*', which means any number of repetitions of the character or subexpression in parentheses that precedes it. For example, the expression '345*6' means that after the substring '34' there are zero or more digits '5', followed by the digit '6'. The expression '3(45)*6' means that after the digit '3' there can be zero or more repetitions of the substring '45', followed by the digit '6'.
4. The symbol '|', which means the 'OR' operation. The priority of this operation is lower than the priority of the implicit concatenation operation. For example, the expression '12|345' means the string '12' or the string '345'. The expression '(12|34)5' means that either '12' or '34' comes first, followed by the digit '5'.

One of the applications of regular expressions is to check whether a string matches a given pattern. For example, to check whether an entered non-negative integer is even, you can write the following expression (leading zeros are allowed for simplicity): (0|1|2|3|4|5|6|7|8|9)*(0|2|4|6|8)

Your task is to solve a more complex problem. You need to determine whether it is possible to rearrange the digits in a non-negative integer so that the number is divisible by 6. For example, in the number 123, the digits can be rearranged in the required way, but in the number 31, they cannot. Write a regular expression to perform this check.

Little girl Kristina came to visit her grandmother and saw antique mechanical clock with two hands on the dial — hour and minute. The clock was working properly, and the movement of the hands of such clocks is continuous (not discrete), that is, for example, in 1 minute the minute hand moves uniformly by 6 degrees, and the hour hand — by 0.5 degrees. At the moment of observation, the clock showed exactly h hours, m minutes, 0 seconds (that is, the minute hand pointed exactly to the mark of m minutes on the dial). For example, the clock in the picture below shows 8 hours 23 minutes and 0 seconds.

Kristina became interested in what is the nearest moment in time when the clock readings will be such that the minimum angle between the hands will be exactly k degrees. But since she is still little, you will have to help her solve this problem.

A certain tropical republic is an archipelago consisting of several (at least two) islands. The map of the archipelago is represented by an $$$n \times m$$$ matrix, where the symbol '1' means land and the digit '0' means water. Any two adjacent cells with the symbol '1' belong to the same island.

The newly elected president of the republic promised to connect all the islands with bridges during the election campaign. Now the promise needs to be fulfilled, but there is not much money in the country. Therefore, he decided to start with the construction of the smallest bridge. Determine the smallest number of cells that need to be changed from '0' to '1' so that any two islands (or more) are connected.

Vasya calculates the sum 2+22+202+2002+...20...02 and wants to see his lucky four-digit number $$$N$$$ among the consecutive digits of the resulting sum. Help Vasya determine the minimum number of summands he needs to take in order to have a fragment in the decimal representation of the sum that coincides with his lucky number $$$N$$$.

At the elective course in electronics, students have developed an unusual calculator. It displays not one number on the screen, but two, and supports three types of commands:

1. from (m, n) get (m - n, n)
2. from (m, n) get (m + n, n)
3. from (m, n) get (n, m)

Determine the sequence of commands to obtain the pair (c, d) from the pair of numbers (a, b).

There are $$$N$$$ cards on the board, each with two integers written on it — one on the left and one on the right. One of the cards has the word "Prize" written on the back.

Two players are playing the game. The host whispers the left number on the prize card to the first player and the right number to the second player. The players are not allowed to explicitly tell each other their numbers, but they can give hints. If both players guess the prize card, they will share the prize between them. The less obvious the hints are, the more valuable the prize will be.

Once, during one of the games, the following dialogue took place between the players:

• Player 1: I know that you don't know the prize card. And I don't know it either.
• Player 2: Thank you, now I know the prize card.
• Player 1: Thank you, now I know it too.

After this, one of the spectators in the audience exclaimed, "I know it too!" Can you determine the prize card?

Perhaps you are familiar with the following well-known problem. A traveler rented a room in a hotel for a week and offered the owner a chain of seven silver rings as payment — one ring per day, with the condition, however, that payment would be made daily. What is the minimum number of rings in the chain that he will have to cut?

The solution to this problem is as follows. It turns out that it is sufficient to cut only one ring — the third one. Then the traveler will have three pieces of chain — consisting of two, one, and four rings. On the first day, he will give the owner one ring. On the second day, he will give the piece consisting of two rings and take back the ring he gave on the first day, and so on.

You are asked to solve this problem in general. Let the chain consist of $$$N$$$ rings, and the traveler wants to stay in the hotel for $$$N$$$ days. Determine the minimum number of cuts required, as well as which rings to cut.

You are given the source code of a program in several popular programming languages. This program reads two integers $$$a$$$ and $$$n$$$ and then outputs one integer — the answer.

With large input numbers, this program can take a long time to run. Your task is to write an alternative program that will produce exactly the same answers, but will run for no more than one second for any input $$$a$$$ and $$$n$$$ in the range from $$$0$$$ to $$$10^{18}$$$.

Text in C++:

#include <iostream>

int main() {
    long long a, n;
    std::cin >> a >> n;
    long long b = 0;
    for (long long i = 0; i < n; i++) {
        b = (b - a) & a;
    }
    std::cout << b << std::endl;
}

a = int(input())
n = int(input())
b = 0
for _ in range(n):
    b = (b - a) & a
print(b)

Text in Java:

import java.util.Scanner;

public class Solution {  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long a = in.nextLong();
        long n = in.nextLong();
        long b = 0;
        for (long i = 0; i < n; i++) {
            b = (b - a) & a;
        }
        System.out.println(b);
    }  
}

Text in C#:

using System;

public class Solution {
    static void Main() {
        long a = long.Parse(Console.ReadLine());
        long n = long.Parse(Console.ReadLine());
        long b = 0;
        for (long i = 0; i < n; i++) {
            b = (b - a) & a;
        }
        Console.WriteLine(b);
    }
}

Text in Pascal:

var
    a, b, n, i: int64;
begin
    read(a, n);
    b := 0;
    i := 0;
    while i < n do begin
        b := (b - a) and a;
        inc(i);
    end;
    writeln(b);
end.