// Copyright (C) 2014 by Alexandru Cojocaru

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

use std::io;
use std::iter;
use std::cmp::Ordering::*;

struct Tst<V> {
    l: Option<Box<Tst<V>>>,
    d: Option<Box<Tst<V>>>,
    r: Option<Box<Tst<V>>>,
    c: char,
    v: Option<V>,
}

impl<V> Tst<V> {
    fn new(c: char) -> Tst<V> { Tst { l: None, d: None, r: None, c: c, v: None } }
}

fn insert<'a, V> (t: &'a mut Option<Box<Tst<V>>>, key: &str, val: V) -> () {	
    let (c, nkey) = key.slice_shift_char().unwrap();

    if t.is_none () {
	*t = Some (Box::new(Tst::new (c)));
    }

    match *t {
	Some (ref mut r) => {
	    match c.cmp(&r.c) {
		Less => { insert (&mut r.l, key, val); }
		Greater => { insert (&mut r.r, key, val); }
		Equal => {
		    if ! nkey.is_empty () {
			insert (&mut r.d, nkey, val);
		    } else {
			r.v = Some(val);
		    }
		}
	    }
	    
	    return;
	}
	None => {
	    panic!("cannot happen");
	}
    }
}

fn get_mut<'r, V> (t: &'r mut Option<Box<Tst<V>>>, key: &str) -> Option<&'r mut V> {
    let (c, nkey) = key.slice_shift_char().unwrap();

    match *t {
	Some (ref mut r) => {
	    match c.cmp(&r.c) {
		Less => get_mut (&mut r.l, key),
		Greater => get_mut (&mut r.r, key),
		Equal => {
		    if nkey.is_empty () {
			r.v.as_mut()
		    } else {
			get_mut (&mut r.d, nkey)
		    }
		}
	    }
	}
	None => None,
    }
}

fn addword<'a> (widx: &mut Option<Box<Tst<Vec<u32>>>>, word: &str, idx: u32) {
    if match get_mut (widx, word) {
	Some(idxs) => {
	    if idxs[idxs.len()-1] != idx {
		idxs.push(idx);
	    }
	    false
	}
        None => true,
    }
    {
	insert (widx, word, vec![idx]);
    } else {
	()
    }

}

fn index (widx: &mut Option<Box<Tst<Vec<u32>>>>) {
    use std::io::BufRead;
    use std::ascii::AsciiExt;
    let mut npage = 1;
    let mut nline = 1;
    let stdin = io::stdin();
    let sl = stdin.lock().lines();
    for l in sl {
	for w in l.unwrap().split(|c: char| !c.is_alphabetic()).filter(|w| !w.is_empty()) {
	    addword (widx, &w.to_ascii_lowercase(), npage);
	}
	nline += 1;
	if nline > 40 {
	    npage += 1;
	    nline = 1;
	}
    }
}

fn print (k: &str, v: &Vec<u32>) {
    if v.len() > 100 {
	return;
    }
    print!("{}: ", k);
    print! ("{}", v[0]);
    for i in v[1..v.len()].iter () {
	print!(", {}", i);
    }
    println!("");
}

fn tstiter<F>(t: &Option<Box<Tst<Vec<u32>>>>, f: F, key: &mut String)
    where F: Fn(&str, &Vec<u32>)
{
    match *t {
	Some(ref r) => {
	    if r.v.is_some () {
		key.push (r.c);
		f (key, r.v.as_ref().unwrap ());
		key.pop ();
	    }
	    
	    if r.l.is_some () {
		tstiter (&r.l, |k,v| f(k,v), key);
	    }
	    
	    if r.d.is_some () {
		key.push (r.c);
		tstiter (&r.d, |k,v| f(k,v), key);
		key.pop ();
	    }
	    
	    if r.r.is_some () {
		tstiter (&r.r, |k,v| f(k,v), key);
	    }
	}
	None => (),
    }
}

fn main ()
{
    let mut widx: Option<Box<Tst<Vec<u32>>>> = None;
    index (&mut widx);
    tstiter (&widx, print, &mut String::new());
}