Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P172PROD - ROUND 2D - Trò chơi thú vị

Hôm nay trong giờ Toán, thầy Ryze dạy về tính chia hết. Đây là một phép toán đơn giản. Để cho bài học thêm thú vị, thầy Ryze đã nghĩ ra 1 trò chơi cho Zed và Shen như sau:

Ban đầu Zed viết một chuỗi s1 chứa đúng chín chữ số và đại diện cho 1 số không vượt quá a. Sau đó, Shen viết một chuỗi s2, chứa đúng chín chữ số và đại diện cho 1 số không vượt quá b. Cho trước a và b, s1 và s2 được chọn bởi Zed và Shen. Các chuỗi được phép chứa 0 ở đầu.

Nếu một số thu được từ việc nối s1 và s2 với nhau mà chia hết cho mod thì Shen thắng, nếu không thì Zed thắng. Cho a, b, mod. Bạn hãy giúp thầy Ryze tìm ra người giành chiến thắng nếu cả Zed và Shen đều chơi theo cách tối ưu. Nếu Zed thắng hãy tìm ra chuỗi nhỏ nhất ( theo thứ tự từ điển) để cậu thắng.

Input

Dòng đầu tiên chứa 3 số nguyên a, b, mod (0 ≤ a, b  ≤ 10 9 , 1 ≤  mod  ≤ 10 7).

Output

Nếu Zed thắng, in ra “1” và chuỗi nhỏ nhất (theo thứ tự từ điển) mà cậu đã viết để giành chiến thắng. Nếu Shen thắng, in ra “2”.

Example

Test 1:
Input:
4 1 4
Output:
2
Test 2:
Input:
4 7 9
Output:
1 000000001
Test 3:
Input:
1 0 1
Output:
2


Được gửi lên bởi:adm
Ngày:2017-02-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.