from bisect import bisect, bisect_left, bisect_right from collections import defaultdict, deque, Counter from copy import deepcopy from functools import lru_cache, reduce from heapq import heapify, heappop, heappush from itertools import accumulate, combinations, permutations, zip_longest import itertools import math import operator from sys import setrecursionlimit import copy # https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py import math from bisect import bisect_left, bisect_right, insort from typing import Generic, Iterable, Iterator, Sequence, Tuple, TypeVar, Union, List T = TypeVar('T') class dsu(): n=1 parent_or_size=[-1 for i in range(n)] def __init__(self,N): self.n=N self.parent_or_size=[-1 for i in range(N)] def merge(self,a,b): assert 0<=a0: result2.append(result[i]) return result2 class multiset(Generic[T]): BUCKET_RATIO = 50 REBUILD_RATIO = 170 def _build(self, a=None) -> None: "Evenly divide `a` into buckets." if a is None: a = list(self) size = self.size = len(a) bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO))) self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)] def __init__(self, a: Iterable[T] = []) -> None: "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)" a = list(a) if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)): # type: ignore a = sorted(a) # type: ignore self._build(a) def __iter__(self) -> Iterator[T]: for i in self.a: for j in i: yield j # type: ignore def __reversed__(self) -> Iterator[T]: for i in reversed(self.a): for j in reversed(i): yield j def __len__(self) -> int: return self.size def __repr__(self) -> str: return "SortedMultiset" + str(self.a) def __str__(self) -> str: s = str(list(self)) return "{" + s[1 : len(s) - 1] + "}" def _find_bucket(self, x: T) -> List[T]: "Find the bucket which should contain x. self must not be empty." for a in self.a: if x <= a[-1]: # type: ignore return a return self.a[-1] def __contains__(self, x: T) -> bool: if self.size == 0: return False a = self._find_bucket(x) i = bisect_left(a, x) # type: ignore return i != len(a) and a[i] == x def count(self, x: T) -> int: "Count the number of x." return self.index_right(x) - self.index(x) def add(self, x: T) -> None: "Add an element. / O(√N)" if self.size == 0: self.a = [[x]] self.size = 1 return a = self._find_bucket(x) insort(a, x) self.size += 1 if len(a) > len(self.a) * self.REBUILD_RATIO: self._build() def discard(self, x: T) -> bool: "Remove an element and return True if removed. / O(√N)" if self.size == 0: return False a = self._find_bucket(x) i = bisect_left(a, x) # type: ignore if i == len(a) or a[i] != x: return False a.pop(i) self.size -= 1 if len(a) == 0: self._build() return True def lt(self, x: T) -> Union[T, None]: "Find the largest element < x, or None if it doesn't exist." for a in reversed(self.a): if a[0] < x: # type: ignore return a[bisect_left(a, x) - 1] # type: ignore def le(self, x: T) -> Union[T, None]: "Find the largest element <= x, or None if it doesn't exist." for a in reversed(self.a): if a[0] <= x: # type: ignore return a[bisect_right(a, x) - 1] # type: ignore def gt(self, x: T) -> Union[T, None]: "Find the smallest element > x, or None if it doesn't exist." for a in self.a: if a[-1] > x: # type: ignore return a[bisect_right(a, x)] # type: ignore def ge(self, x: T) -> Union[T, None]: "Find the smallest element >= x, or None if it doesn't exist." for a in self.a: if a[-1] >= x: # type: ignore return a[bisect_left(a, x)] # type: ignore def __getitem__(self, x: int) -> T: "Return the x-th element, or IndexError if it doesn't exist." if x < 0: x += self.size if x < 0: raise IndexError for a in self.a: if x < len(a): return a[x] # type: ignore x -= len(a) raise IndexError def index(self, x: T) -> int: "Count the number of elements < x." ans = 0 for a in self.a: if a[-1] >= x: # type: ignore return ans + bisect_left(a, x) # type: ignore ans += len(a) return ans def index_right(self, x: T) -> int: "Count the number of elements <= x." ans = 0 for a in self.a: if a[-1] > x: # type: ignore return ans + bisect_right(a, x) # type: ignore ans += len(a) return ans class bit: def __init__(self, n): self._n = n self.data = [0] * n def add(self, p, x): assert 0 <= p < self._n p += 1 while p <= self._n: self.data[p - 1] += x p += p & -p def sum(self, l, r)->int: assert 0 <= l <= r <= self._n return self._sum(r) - self._sum(l) def _sum(self, r): s = 0 while r > 0: s += self.data[r - 1] r -= r & -r return s class SegTree: def __init__(self, op, e, n, v=None): self._n = n self._op = op self._e = e self._log = (n - 1).bit_length() self._size = 1 << self._log self._d = [self._e()] * (self._size << 1) if v is not None: for i in range(self._n): self._d[self._size + i] = v[i] for i in range(self._size - 1, 0, -1): self._d[i] = self._op(self._d[i << 1], self._d[i << 1 | 1]) def set(self, p, x): p += self._size self._d[p] = x while p: self._d[p >> 1] = self._op(self._d[p], self._d[p ^ 1]) p >>= 1 def get(self, p): return self._d[p + self._size] def prod(self, l, r): sml, smr = self._e(), self._e() l += self._size r += self._size while l < r: if l & 1: sml = self._op(sml, self._d[l]) l += 1 if r & 1: r -= 1 smr = self._op(self._d[r], smr) l >>= 1 r >>= 1 return self._op(sml, smr) def all_prod(self): return self._d[1] def dijkstra(g, c, s): inf = 2 << 60 d = [inf] * len(g) heap = [(0, s)] heapify(heap) while heap: dis, u = heappop(heap) if dis > d[u]: continue d[u] = dis for v in g[u]: if d[v] > d[u] + c[(u, v)]: heappush(heap, (d[u] + c[(u, v)], v)) return d def bfs(g, s): que = deque([s]) d = [-1] * len(g) d[s] = 0 while que: u = que.popleft() for v in g[u]: if d[v] != -1: continue d[v] = d[u] + 1 que.append(v) return d def readweightedgraph(n, m): g = [[] for _ in range(n)] idx = {} cost = {} for i in range(m): a, b, c = map(int, input().split(' ')) a -= 1 b -= 1 g[a].append(b) g[b].append(a) idx[(a, b)] = i idx[(b, a)] = i cost[(a, b)] = c cost[(b, a)] = c return g, idx, cost def readdirgraph(n, m): g = [[] for _ in range(n)] for i in range(m): u, v = map(int, input().split(' ')) g[u - 1].append(v - 1) return g def readnondirgraph(n, m): g = [[] for _ in range(n)] for i in range(m): u, v = map(int, input().split(' ')) g[u - 1].append(v - 1) g[v - 1].append(u - 1) return g def mycom(n, r): if n - r < r: return mycom(n, n - r) return math.factorial(n) // math.factorial(r) // math.factorial(n - r) fac = [] inv = [] finv = [] def cominit(n: int): global fac, inv, finv fac = [0] * (n + 1) inv = [0] * (n + 1) finv = [0] * (n + 1) fac[0] = fac[1] = 1 inv[1] = 1 finv[0] = finv[1] = 1 for i in range(2, n + 1): fac[i] = fac[i - 1] * i % mod inv[i] = mod - mod // i * inv[mod % i] % mod finv[i] = finv[i - 1] * inv[i] % mod def com(n:int, r:int): return fac[n] * finv[r] * finv[n - r] % mod def modpow(a, n, m): ret = 1 while n: if n & 1: ret = ret * a % m a = a * a % m n >>= 1 return ret def listdividers(n: int): assert n > 0 low = [] high = [] for i in range(1, n + 1): if i*i>n: break if not n % i: q = n // i if i == q: low.append(i) else: low.append(i) high.append(q) return low + high[::-1] def lcm(a:int, b:int): return a * b // math.gcd(a, b) def chunked(l, n: int): for i in range(0, len(l), n): yield l[i:i + n] def narytoint(a:str, b:int): ans = 0 for c in a: ans *= b ans += int(c) return ans def narytostr(a:int, b:int): if a == 0: return '0' s = [] while a: s.append(str(a%b)) a //= b return ''.join(reversed(s)) def mulmat(a: Sequence[Sequence], b: Sequence[Sequence]): assert len(a[0]) == len(b) l = len(a) m = len(a[0]) n = len(b[0]) ans = [[0] * n for _ in range(l)] for i in range(l): for j in range(n): for k in range(m): ans[i][j] += a[i][k] * b[k][j] return ans def applymat(a: Sequence[Sequence], b: Sequence): pass def xgcd(a, b): x0, y0, x1, y1 = 1, 0, 0, 1 while b != 0: q, a, b = a // b, b, a % b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return a, x0, y0 def modinv(a, m): g, x, _ = xgcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m def lcs(a: str, b:str): n = len(a) m = len(b) dp = [0] * (m + 1) for i in range(n): nxt = [0] * (m + 1) for j in range(m): if a[i] == b[j]: nxt[j+1] = dp[j] + 1 else: nxt[j+1] = max(dp[j+1], nxt[j]) dp = nxt return dp[m] def pfact(n:int): if n <= 1: return {} cur = n ans = defaultdict(int) for i in range(2,n+1): if i*i>n: break while not cur % i: cur //= i ans[i] += 1 if cur != 1: ans[cur] += 1 return dict(ans) def bubblesort(x: List): l = len(x) for i in range(l-1): for j in range(l-1-i): if x[j] > x[j+1]: x[j], x[j+1] = x[j+1], x[j] def perm2(n, s, cur, x, r): if len(x) == n-1: r.append(x+[s-cur]) return for i in range(s-cur+1): x.append(i) cur += i perm2(n, s, cur, x, r) x.pop() cur -= i def arithmetic_sum(a, d, n): return n*(2*a+(n-1)*d)//2 def clamp(x, mn, mx): return mn if x < mn else mx if mx < x else x def isin(x, mn, mx): return mn <= x and x < mx def list_primes(limit): primes = [] is_prime = [True] * (limit + 1) is_prime[0] = False is_prime[1] = False for p in range (0, limit + 1): if not is_prime[p]: continue primes.append(p) for i in range(p*p, limit + 1, p): is_prime[i] = False return primes def z_algorithm(s:str): z = [0]*len(s) i = 1 j = 0 z[0] = len(s) while i < len(s): while i+j < len(s) and s[i+j] == s[j]: j += 1 z[i] = j if j == 0: i += 1 continue k = 1 while k < j and k+z[k] < j: z[i+k] = z[k] k += 1 i += k j -= k return z def exgcd(a:int, b:int): if b == 0: return a, 1, 0 d, y, x = exgcd(b, a%b) y -= a//b*x return d, x, y # def crt(V:Sequence[Tuple[int, int]]): # x = 0; d = 1 # for X, Y in V: # a, b, g = exgcd(d, Y) # x, d = (Y*b*x + d*a*X) // g, d*(Y // g) # x %= d # return x, d # def crt2(b1:int, m1:int, b2:int, m2:int): # x, y, d = exgcd(m1, m2) # if (b2-b1) % d != 0: # return (0, 0) # m = m1 * (m2//d) # tmp = (b2-b1)//d*x%(m2//d) # r = (b1 + m1 * tmp) % m # print(x, y, d, m, tmp, r) # return (r, m) def crt(r: Sequence[int], m: Sequence[int]): x, y = 0, 1 for rr, mm in zip(r, m): d, p, q = exgcd(y, mm) if (rr-x) % d != 0: return (0, 0) tmp = (rr-x)//d*p x += y * tmp y *= mm//d x %= y return (x, y) mod = 998244353 # mod = 10**9+7 inf = 1 << 60 setrecursionlimit(1000000) x, y = zip(*tuple(map(int, (input().split(' '))) for _ in range(3))) if not any(x): print(math.gcd(*x)) exit() r, m = crt(x, y) if m == 0: print(-1) else: print(r)