KATHMANDU - Nepal was thrown into political limbo on Saturday after the Maoists quit the interim government of the newly republican nation and demanded the prime minister's resignation. Nepal's former Maoist rebels stormed out of the government late on Friday, accusing a rival party of clinging to power despite being defeated in landmark elections in the Himalayan country two months ago. "Prime Minister Girija Prasad Koirala must resign to open the way for the formation of a new government," senior Maoist official Dinanath Sharma told AFP after the ultra-leftists announced their resignations. Nepal abolished its monarchy three weeks ago, but the country's two most powerful parties the Maoists and the prime minister's Nepali Congress party have been unable to reach a deal on power-sharing. The Maoists, who dominate the new assembly elected in April, say they have the right to lead the government and choose a new president. They say the wrangling is preventing the assembly from starting work on its chief task of rewriting Nepal's constitution. "The constituent assembly has not been able to begin drafting a new constitution because of these power-sharing problems," said Sharma. Nepali Congress officials say Koirala regarded by many as the architect of a peace deal that ended a deadly civil war waged by the Maoists and led to the creation of the new republic deserves to be Nepal's first president. "The Maoist decision has shocked us, the political impasse has deepened but that doesn't mean we are out of solutions," said Nepali Congress spokesman Arjun Nasingh Khatri Chettri. The Congress, Nepal's oldest political party which has half as many seats as the Maoists in the 601-member assembly that will chart Nepal's political future, said the Maoists' move to leave the government was premature. "Talks with the Maoists were going positively and yet they resigned from the government just when we were nearing a conclusion," said the Congress spokesman. The president's role is a crucial one because the person occupying the office is expected to be commander of the armed forces. "This deadlock is creating uncertainty but we are always ready to reach a consensus through mutual understanding," said Maoist official Sharma. The Congress official was also hopeful a breakthrough would be reached after discussions. "The only option we have is to resolve all political issues through dialogue. We hope to come to a logical conclusion in the next few days," said Khatri Chettri. The end of Nepal's monarchy late last month was the culmination of a rocky peace process between the former rebels, whose "People's War" claimed at least 13,000 lives, and mainstream political parties. The two sides united in late 2005 after now-deposed king Gyanendra seized direct control of the impoverished nation, an unpopular move that ultimately led to the demise of the 240-year-old monarchy.