Under construction

Still being built. Things may change

Attention

Interview

Time limit1sMemory limit512 MB

Summary
Count the ingredient triples whose positions increase in both recipe books, or report that no such triple exists.
Level

Medium5 of 10

Topics
Dynamic programming, Segment tree
Solved
No attempts yet

Problem

Sangjini likes newcomers. After learning that newcomers like cookies, Sangjini plans to catch their attention by giving them a cookie in a flavor they enjoy.

Each cookie is made from exactly 33 ingredients, and each ingredient is written as an integer.

A survey of the newcomer's tastes showed that they like a cookie whose ingredients form an increasing subsequence of positions in some recipe book. Each recipe book lists the ingredients as integers from 00 to N−1N - 1.

After trial and error, Sangjini found two recipe books that the newcomer probably likes. Sangjini does not know which one is correct, so to be sure of getting attention, Sangjini will make cookies from the ingredient triples that form an increasing-position subsequence in both recipe books and give them as gifts.

Find how many cookies Sangjini must make to get the newcomer's attention.

You and me, 내 맘이 보이지
한참을 쳐다봐, 가까이 다가가, you see?
Ayy-yeah, you see? Ayy, ayy, ayy, ayy
One, two, three, 용기가 생겼지
이미 아는 네 눈치 고개를 돌려 천천히, 여기
You see? 여기 보이니?

Looking for attention, 너야겠어
확실하게 나로 만들겠어
A-T-T-E-N-T-I-ON
Attention is what I want
A-T-T-E-N-T-I-ON
You got me looking for attention

Input

The first line contains an integer NN, the length of each recipe book. (3≤N≤100 000)(3\leq N\leq 100\,000)

The second and third lines list the ingredients of each recipe book in order.

Each recipe book lists the integers from 00 to N−1N - 1 exactly once each.

Output

If a cookie that can get the newcomer's attention exists among the cookies from the original recipe and the modified recipe, print "My heart has gone to paradise" on the first line, and print the number of cookies Sangjini must make on the second line.

If Sangjini cannot find a cookie that is certain to get attention, print "Attention is what I want".

Hint

The seven recipes for the cookies that must be made in the second sample are as follows.

1 2 3
1 2 0
1 2 4
1 3 0
1 3 4
2 3 0
2 3 4

Examples2

  1. Example 1

    Input
    3
    1 2 0
    0 1 2
    
    Expected output
    Attention is what I want
    
  2. Example 2

    Input
    5
    1 2 3 0 4
    1 2 3 4 0
    
    Expected output
    My heart has gone to paradise
    7