You are designing a new music app for your startup called Bungus, and one of your killer features is an experimental autoplay for playlists, designed to make song transitions as gentle as possible by only transitioning between similar songs.

Specifically, you have ~n~ songs, listed from song ~1~ to song ~n~, that you want to use to create a playlist, and you can include any song any amount of times (including zero). However, the playlist must begin with the first song (song ~1~) and end with the final song (song ~n~). Each song has an energy value ~a_i~, and when you transition between two songs a dissatisfaction of ~|a_i - a_j|~ is incurred.

Note that customers remember playlists based on their most extreme memories, so the overall dissatisfaction incurred is the maximum single transition dissatisfaction score in the playlist.

Moreover, from previous studies, you have decided that listeners can only tolerate transitions between songs sharing either:

• the same artist;
• the same genre;
• or the same year.

Find the minimum possible overall dissatisfaction score you can incur while arranging the playlist.

Input

The first line contains a single integer ~n~ ~(2 \leq n \leq 10^5)~, the amount of songs you have available to create your playlist.

The next ~n~ lines each contain details of a single song, from song ~1~ through to song ~n~. Each line consists of ~a_i~, ~\text{artist}_i~, ~\text{genre}_i~ and ~\text{year}_i~, where

• ~1 \leq a_i \leq 10^9~ is the energy score
• ~\text{artist}_i~ and ~\text{genre}_i~ are strings of upper or lowercase characters between ~1~ and ~20~ characters long representing the artist and genre, and
• ~1 \leq \text{year}_i \leq 3000~ is the release year.

Output

Output a single integer — the minimum possible overall dissatisfaction score that can be incurred when transitioning through a created playlist. The dissatisfaction score is the maximum absolute difference between the energy values of any two consecutive songs in the created playlist, and songs can only be arranged consecutively if they share a property. Each song can be used as many times as required (or zero, besides songs ~1~ and ~n~).

If it is impossible to arrange the playlist while maintaining the above properties, output -1.

Examples

Input 1

4
10 TaylorSwift Pop 2000
25 Eminem HipHop 2001
30 BrunoMars Pop 2001
40 SnoopDogg HipHop 1999

Output 1

20

In this case, an optimal playlist that you can create is 1 3 2 4. ~1\to 3~ works as they are both Pop, ~3\to 2~ works as they are both released in ~2001~, and ~2\to 4~ works as they are both HipHop. The maximum dissatisfaction score is from ~1\to 3~ ~(|10 - 30|=20)~. There is no better way to create a playlist starting at ~1~ and ending at ~n~.

Input 2

3
5 JustinBieber RandB 2016
100 LadyGaga Jazz 2016
6 LedZeppelin Rock 1971

Output 2

-1

Song ~1~ can transition into song ~2~ as they are both released in ~2016~, but it is impossible for either to transition into song ~n~ so the playlist cannot be constructed.

Input 3

5
10 A G1 2000
17 A G2 2001
30 B G1 2002
18 C G2 2002
19 D G3 2002

Output 3

7

There are multiple valid arrangements. One is ~1\to 3\to 5~ with max dissatisfaction ~\max(|10-30|, |30-19|)=20~. Another is ~1\to 2\to 4\to 5~ with max dissatisfaction ~\max(|10-17|, |17-18|, |18-19|)=7~. The only songs that can follow ~1~ are ~2~ (same artist) and ~3~ (same genre), so any playlist must incur at least ~|10-17|=7~ on its first transition. Therefore, the second path is optimal.