using System; using System.Collections.Generic; class test{ static void Main(){ new Sol().Solve(); } } class Sol{ public void Solve(){ int N=(int)1e6; Dictionary D=new Dictionary(N*2); for(long x=1;x