B - Big Integers

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

長さ N の整数列 A、長さ M の整数列 B、整数 K が与えられます。 値 X,Y を以下のように定義します。

  • X= \sum_{i=1}^N A_i \times K^{N-i} = A_1 \times K^{N-1} + A_2 \times K^{N-2} + ... + A_N \times K^0
  • Y= \sum_{i=1}^M B_i \times K^{M-i} = B_1 \times K^{M-1} + B_2 \times K^{M-2} + ... + B_M \times K^0

XY のどちらが小さいかを求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 2 \leq K \leq 10^9
  • 0 \leq A_i \leq K-1
  • 1 \leq A_1
  • 0 \leq B_i \leq K-1
  • 1 \leq B_1
  • 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M K
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_M

出力

X < Y のときは XX > Y のときは YX = Y のときは Same と出力せよ。


入力例 1

3 3 10
1 2 3
1 2 4

出力例 1

X

X=123,Y=124 であり、 X<Y であるので X と出力します。


入力例 2

4 3 13
1 2 3 4
4 5 6

出力例 2

Y

入力例 3

4 4 2
1 1 0 1
1 1 0 1

出力例 3

Same