Prime Factor Recurrence

Consider a sequence \(f\) defined by the recurrence \(f_n = a_n \cdot f_{n-1} + b_n\) for \(n \ge 1\). For a given positive integer \(k\), you are provided with three sequences \(a_1,a_2,\dots,a_k\), \(b_1,b_2,\dots,b_k\), and a sequence of primes \(p_1,p_2,\dots,p_k\).

The term \(f_i\) can be written in the form \[ f_i = A_i\,f_0 + B_i, \quad\text{where } A_i = a_i a_{i-1}\cdots a_1, \quad B_i = a_i B_{i-1} + b_i \text{ with } B_0=0 and \ A_0=1. \]

Your task is to determine whether there exists a nonnegative integer \(f_0\) such that for every \(1\le i\le k\), the number \(f_i\) is a multiple of the prime \(p_i\); i.e., \[ p_i\mid f_i \quad\text{for } 1 \le i \le k. \]

inputFormat

The first line contains an integer \(k\) (\(1\le k\le 10^5\)), the number of recurrence steps.

Each of the next \(k\) lines contains three space-separated integers \(a_i\), \(b_i\), and \(p_i\), where \(p_i\) is a prime number. The recurrence is defined as \(f_i = a_i \cdot f_{i-1}+b_i\) for \(i\ge1\).

outputFormat

Output a single line containing YES if there exists a nonnegative integer \(f_0\) that satisfies the condition for every \(i\) (\(1\le i\le k\)); otherwise, output NO.

sample

2
2 3 5
3 4 7

YES