During the formation of the empire, the Khmer had close cultural, political, and trade relations with Java and with the Srivijaya empire that lay beyond Khmer's southern seas. In 851 an Arabic merchant named Sulaimaan recorded an incident involving a Khmer king and a Maharaja of Zabaj. He described the story of a Khmer king who defied the power of Maharaja of Zabaj. It was said that the Javanese Sailendras staged a surprise attack on the Khmers by approaching the capital from the river. The young king was later punished by the Maharaja, and subsequently the kingdom became a vassal of the Sailendra dynasty. Zabaj is the Arabic form of Javaka and might refer to Java or Srivijaya. The legend probably describes the predecessor or initial stage of the Khmer kingdom under Javanese dominion. The Legend of the Maharaja of Zabaj was later published by the historian Masoudi in his 947 book, "Meadows of Gold and Mines of Gems." The Kaladi inscription of Java (c. 909 CE) mentioned "Kmir" (Khmer people or Cambodian) together with "Campa" (Champa) and "Rman" (Mon) as foreigners from mainland Southeast Asia who frequently came to Java to trade. The inscription suggests a maritime trade network had been established between Kambuja and Java (Mdang kingdom). In 916 CE Arab historian Abu Zaid Hasan, recorded in a lengthy chronicle that the young, inexperienced king of Khmer, is hostile to Java. When the hostility becomes state policy and is known publicly, the King of Java attacked and captured the Khmer king. He was beheaded and the head brought to Java. The King of Java ordered the Minister of Khmer Empire to seek the successor. After being cleaned and embalmed, the head of the king was put in a vase and sent to the new Khmer king.