from sys import *
from math import *
from random import *
from socket import *
from time import *

import struct

def euclid(a, b):
	if b == 0:
		if a >= 0:
			return [a,1,0]
		else:
			return [-a,-1,0]
	else:
		r0 = a
		r1 = b
		x0 = 1
		x1 = 0
		y0 = 0
		y1 = 1
		while r1 != 0:
			q = r0/r1
			r2 = r0 - q*r1
			x2 = x0 - q*x1
			y2 = y0 - q*y1
			r0 = r1
			r1 = r2
			x0 = x1
			x1 = x2
			y0 = y1
			y1 = y2
		if r0 < 0:
			r0 = -r0
			x0 = -x0
			y0 = -y0
		return [r0,x0,y0]

def mod(a, m):
	return a%m


def modmul(a, b, m):
	return mod(a*b,m)

def modinv(a, m):
	ls = euclid(a,m)
	if ls[0] != 1:
		print 'modinverr'
		exit(0)
	else:
		return mod(ls[1],m)
		
def moddiv(a, b, m):
	return modmul(a,modinv(b,m),m)

def powermod(a, e, m):
	if e < 0:
		a = modinv(a,m)
		e = -e
	x = 1
	b = a
	while e > 0:
		if e%2 == 1:
			x = modmul(x,b,m)
		b = modmul(b,b,m)
		e /= 2
	return x


def longsqrt(a):
        if a < 0:
                print 'sdfsdf'
                exit()
        else:
                if a <= 1:
                	return a
                s = a
                while s*s > a:
                	s = (s + a/s)/2
        return s

def ElGamalDecrypt(u, v, p, s):
	return modmul(powermod(u,p-1-s,p),v,p)

def chinese(a, b, m, n):
	e = euclid(m, n)
	d = e[0]
	if d != 1:
		print 'zxczxc'
		exit()
	else:
		u = e[1]
		v = e[2]
		return mod(a*n*v+b*m*u, m*n)

def multichinese(am):
	if len(am) == 1:
		return mod(am[0][0], am[0][1])
	am1 = am[1:]
	k = len(am1)
	mm = 1
	for i in range(0, k):
		mm *= am1[i][1]
	x1 = multichinese(am1)
	return chinese(am[0][0], x1, am[0][1], mm)

##### Pohlig-Hellman @ #####

def GetSecret(p, y):
	g = 2
	q = []
	m = p-1
	r = 2
	s = longsqrt(m)
	while r <= s:
		if m % r == 0:	
			e = 0
			while m % r == 0:
				m /= r
				e += 1
			q.append([r,e])
			s = longsqrt(m)
		r += 1
	if m > 1:
		q.append([m,1])

	t0 = time()
	ls = []	
	for re in q:
		r = re[0]
		e = re[1]
		m = p-1
		mm = m/(r**e)
		ymm = powermod(y,mm,p)
		gmm = powermod(g,mm,p)
		gg = powermod(g,m/r,p)
		xr = 0
		for i in range(0,e):
			m /= r
			yy = moddiv(powermod(ymm,m/mm,p),powermod(gmm,(m/mm)*xr,p),p)
			ggj = 1			
			for j in range(0,r):
				if yy == ggj:		
					xr += j * (r**i)
					break
				ggj = modmul(ggj,gg,p)
		ls.append([xr,r**e])

	x = multichinese(ls)
	return x

msgenc = '(16777259,2,8572031) (8528712,11633764);(11912890,16147792);(5329917,4927963);(1816982,6221827);(11081954,14768326);(10573461,10057203);(8305938,8404152);(9931321,16087922);(2450572,14991352);(4516958,8493460);(3195906,6497578)'
pubkey = msgenc.split(' ')[0]
p  = pubkey.split(',')[0][1:]
print "p =", p
msg=msgenc.split(' ')[1]
y=pubkey.split(',')[2][:-1]
print "y =", y
x = GetSecret(int(p),int(y))
print "x =", x
ccs=msg.split(';')
flag = ''
for cc in ccs:
	(c1,c2) = cc.split(',')
	res=ElGamalDecrypt(int(c1[1:]),int(c2[:-1]),int(p),int(x))
	flag = flag + struct.pack('I',res).strip('\0')
print "Flag =",flag