Under construction

Still being built. Things may change

Hula's Cardgame

Time limit2sMemory limit512 MB

Summary
Given tables whose three cards point to tables at or above their own number, decide for each E whether Geunsu can reach table E while Seunghyeong deletes one card per move.
Level

Hard8 of 10

Topics
Game theory, Graph, DFS
Solved
No attempts yet

Problem

Geunsu and Seunghyeong want to play Hula's Cardgame at K512. K512 has NN tables, numbered from 11 to NN. Each table has 3 cards, and each card on table ii holds an integer from ii to NN, inclusive.

Geunsu and Seunghyeong are at table 11 now. Table EE has a Umaru Doma doll that Geunsu likes, so Geunsu wants to go to table EE. Seunghyeong dislikes this and does not want to go to table EE. They repeat the following steps until the game ends.

  1. If the current table is table EE, Geunsu wins.
  2. If the current table is not table EE, Seunghyeong removes one of the 3 cards on the current table.
  3. Geunsu picks one of the 2 remaining cards on the current table. They move to the table whose number is the integer on that card. If the integer on the chosen card equals the current table number, meaning they revisit a table they have already visited, Seunghyeong wins.

Assume both play optimally. Geunsu wants to know whether he can win. Solve this for every EE with 1≤E≤N1 \le E \le N.

Input

The first line contains the number of tables NN. (1≤N≤2×1051 \le N \le 2\times10^5)

From the second line to the (N+1)(N+1)th line, the integers aia_i, bib_i, cic_i on the 3 cards of each table are given, separated by spaces. The jjth line gives the 3 integers on the cards of table j−1j-1. (i≤ai,bi,ci≤Ni \le a_i, b_i, c_i \le N)

Output

On the iith line, print Yes if Geunsu can win when E=iE = i, and No if he loses.

Examples2

  1. Example 1

    Input
    6
    2 3 4
    2 2 3
    4 5 6
    4 5 6
    5 6 6
    6 6 6
    
    Expected output
    Yes
    No
    No
    No
    No
    Yes
    
  2. Example 2

    Input
    6
    2 3 4
    2 3 3
    4 5 6
    5 5 5
    6 6 6
    6 6 6
    
    Expected output
    Yes
    No
    Yes
    No
    Yes
    Yes