This page is still under construction.

Parts of this page are still being built. What you see may change.

Prime Palindrome Flags

Time limit1sMemory limit128 MB

Summary
Given n and an optional middle digit c, output the largest n-digit-palindromic number that is prime if any such palindrome is prime, otherwise the largest palindrome.
Level

Medium6 of 10

Topics
Math, Number theory, Brute force, Implementation
Solved
No attempts yet

Problem

At the athletics festival of J Middle School, each class plays the following class-versus-class contest. A class chooses nn boy–girl representative pairs

(b1,g1), (b2,g2), …, (bn,gn).(b_1, g_1),\ (b_2, g_2),\ \dots,\ (b_n, g_n).

Every student freely chooses a flag printed with a single digit from 00 to 99 (there are plenty of flags of each digit) and they line up in one horizontal row. The two students of a pair must hold flags showing the same digit, so gi=big_i = b_i. The row is ordered as

b1 b2 … bn  c  gn … g2 g1,b_1\ b_2\ \dots\ b_n\ \ c\ \ g_n\ \dots\ g_2\ g_1,

that is, the girls stand in the reverse order of the boys. In the middle, the homeroom teacher either stands holding a flag whose digit cc is fixed in advance by the head referee, or is told not to stand at all.

Reading the whole row of digits from left to right as a single integer — it has 2n2n digits (no teacher) or 2n+12n+1 digits (with the teacher) — the class whose integer is prime wins. If both integers are prime, or both are non-prime, the class with the larger integer wins. A leading zero is not allowed (numbers are written in the usual way), so arrangements such as

0 b2 … bn c gn … g2 00\ b_2\ \dots\ b_n\ c\ g_n\ \dots\ g_2\ 0

or

0 b2 … bn gn … g2 00\ b_2\ \dots\ b_n\ g_n\ \dots\ g_2\ 0

are forbidden; hence b1≠0b_1 \neq 0.

Because gi=big_i = b_i, the row of digits is a palindrome b1b2…bn [c] bn…b2b1b_1 b_2 \dots b_n\,[c]\,b_n \dots b_2 b_1. You want your class to never lose. Determine the arrangement that guarantees you do not lose.

Against optimal play the never-losing arrangement is unique. If at least one valid palindrome is prime, it is the largest prime palindrome (a prime always beats a non-prime, and among primes only the largest never loses); otherwise every palindrome is non-prime and it is the largest palindrome.

Input

A single line contains the integer nn and the single-digit integer cc, separated by one space. If c<0c < 0, the teacher does not stand in the middle (the integer then has 2n2n digits); otherwise the teacher stands with the digit cc (the integer has 2n+12n+1 digits).

Constraints: 1≤n1 \le n and −9≤c≤9-9 \le c \le 9. In most cases 1≤n≤41 \le n \le 4.

Output

Print, on a single line, the never-losing arrangement — the row of digits read as one integer.

Examples4

  1. Example 1

    Input
    1 0
    
    Expected output
    101
    
  2. Example 2

    Input
    1 5
    
    Expected output
    757
    
  3. Example 3

    Input
    3 7
    
    Expected output
    9957599
    
  4. Example 4

    Input
    1 -1
    
    Expected output
    11