Input

1
 
 

Output