Under construction

Still being built. Things may change

Plate Parity

Interview

Time limit1sMemory limit512 MB

Summary
Count integers in [A, B] whose rightmost nonzero digit is odd versus even, where A and B go up to 10^16.
Level

Medium4 of 10

Topics
Math, Implementation, Combinatorics, Prefix sum
Solved
No attempts yet

Problem

Odd-even rationing is a common method to restrict resource consumption to half the population on any given day. For example, a private vehicle is allowed to drive, park, or buy gasoline only on alternating days depending on whether its license plate is odd or even. Jakarta enforced this policy to reduce traffic jams during the 2018 Asian Games: odd-plate private vehicles could drive on certain restricted roads during certain hours only on odd dates, and even-plate private vehicles only on even dates.

Despite its effectiveness, some people do not know that zero (0) is an even number, which can cause confusion. That is why we need to investigate a variant of odd-even rationing.

In this problem, whether a license plate is even or odd is determined by its rightmost non-zero digit. If that digit is odd, the license plate is odd; otherwise, the license plate is even. For example:

  • License plate 701038 is even because 8 is even.
  • License plate 701803 is odd because 3 is odd.
  • License plate 801350 is odd because 5 is odd.
  • License plate 3800 is even because 8 is even.

The smallest license plate number is 1, as in the presidential plate "RI 1".

Your task is to determine how many integers between A and B (inclusive) are odd plates and how many are even plates.

Input

The input contains two integers A B (1 ≤ A ≤ B ≤ 10^16), representing the interval [A, B] of plates to investigate.

Output

Output one line with two integers O E separated by a single space: the number of odd plates and the number of even plates.

Examples3

  1. Example 1

    Input
    1 10
    
    Expected output
    6 4
    
  2. Example 2

    Input
    296 311
    
    Expected output
    10 6
    
  3. Example 3

    Input
    946 1073
    
    Expected output
    72 56