OPINION

Among other issues, we must decide whether a federal district court may grant citizenship to resident aliens whose applications were rejected by the Immigration and Naturalization Service in part because of their past terrorist activities.

I

In November 1999, during the pendency of various civil and criminal proceedings arising out of challenges to earlier convictions, the district court naturalized Viken Hovsepian and Viken Yacoubian (the “applicants”) despite the fact that the Immigration and Naturalization Service (the “INS”) had previously denied their applications. To understand the context of such proceedings and the many collateral issues raised by these appeals, a detailed history is in order.

We begin in 1982, when the FBI discovered through intercepted phone conversations that the applicants were planning to blow up the offices of the Honorary Turkish Consul General in Philadelphia. At the time, the applicants were associated with the Justice Commandoes of the Armenian Genocide, a terrorist organization dedicated to exacting revenge against Turkey for atrocities committed against Armenians. The FBI learned that the applicants had arranged for a coconspirator to transport the bomb on a commercial airliner from Los Angeles International Airport to Boston’s Logan Airport on October 22. The FBI failed to detain the coconspirator, and he successfully boarded the flight with the bomb stowed in his checked baggage. However, upon landing, the FBI promptly arrested him and seized the bomb. The FBI later estimated that the bomb likely would have killed between 2000 and 3000 people.

The applicants, who were Lebanese citizens and lawful permanent residents of the United States, were duly convicted of various federal explosives offenses. At the time of conviction, Yacoubian was twenty-*926one and Hovsepian was twenty-four, and thus both were eligible for sentencing under the Federal Youth Corrections Act (FYCA), which pertained to offenders twenty-six years old and under. 18 U.S.C. §§ 4216, 5010 (1982) (repealed 1984). Because Yacoubian was under twenty-two, the court could sentence him as an adult only if it made an explicit finding that he would not benefit from a sentence under the FYCA. § 5010; Dorszynski v. United States, 418 U.S. 424, 425-26, 94 S.Ct. 3042, 41 L.Ed.2d 855 (1974). As for Hovsepian, who was over twenty-two, the court was required to sentence him as an adult unless it concluded that he would benefit from a sentence under the Act. § 4216.

The court sentenced Hovsepian and Ya-coubian as adults. While the court expressly found that Hovsepian would not benefit from a FYCA sentence, the court neglected to make such a finding as to Yacoubian. At sentencing, the court also issued a Judicial Recommendation Against Deportation (JRAD) for both applicants. See 8 U.S.C. § 1251(b)(2) (1982) (repealed 1990). Their convictions made them eligible for deportation for having committed a crime of moral turpitude. 15242 See § 1251(a)(4). The JRAD prohibited the INS from deporting them on this ground. § 1251(a)(4).

Both Hovsepian and Yacoubian have served their full prison terms. Since their release, each has married and lives in California. Neither has since run afoul of the law; indeed, both have established very successful, distinguished careers. Hovse-pian earned a Ph. D. in international relations from the University of Southern California in 1994. He currently manages a hedge fund with a partner who is based in New York. Yacoubian earned a master’s degree in psychology from Loyola Marym-ount University in 1988. He later entered the Ph. D. program at the University of Southern California. He is currently the principal of the Rose and Alex Pilibos Armenian High School and an adjunct professor at Woodbury University. Both submitted numerous glowing character references, many of which detailed their commitment to the Armenian-American community.

In 1988, Congress amended the immigration laws, making unlawful possession of a destructive device a deportable offense. § 1227(a)(2)(C). In 1990, Congress made this ground of deportation retroactive to all aliens regardless of the date of their convictions. Pub.L. No. 101-649, § 602(c), 104 Stat. 4978, 5081-82 (1990). The applicants’ offenses fell within this new category of deportation. In 1991, the INS placed a detainer on Yacoubian, a precursor to deportation, Yacoubian filed suit, claiming that the JRAD barred the INS’s action; the district court permanently enjoined the INS from initiating deportation proceedings. We reversed, holding that the JRAD did not apply to the new ground of deportation. See United States v. Yacoubian, 24 F.3d 1 (9th Cir. 1994).

In 1997, the United States filed a Rule 36 motion under the Federal Rules of Criminal Procedure to correct certain typographical errors in the applicants’ judgment and commitment orders. The motion’s purpose was to assist the INS in initiating deportation proceedings against the applicants. The court denied the motion and chided the government for seeking to deport the applicants. R.T. 8/5/1997 at 10-11 (“[T]he idea of deporting these people is nothing short of lunacy.”).

While the government’s motion was pending, Hovsepian made a Rule 35 motion for a “correction” of Ms sentence. Alternatively, he sought writs of audita querela and coram nobis. He claimed that the district court committed a “mistake of fact” at the time of sentencing. Specifical*927ly, he claimed that the court mistakenly thought that the JRAD would categorically bar the INS from deporting him on the basis of his convictions. As relief, he sought resentencing under the FYCA, and expungement of his conviction.

Yacoubian similarly filed a Rule 35 motion, also seeking resentencing and ex-pungement under the FYCA. He stressed that the court neglected to find at sentencing that he would not benefit from a sentence under the FYCA.

The court granted Hovsepian’s and Ya-coubian’s motions and resentenced both under the FYCA. The court “expunged” their convictions by ordering the FBI to remove their conviction records from its files. The court directed the FBI to place the conviction records in a “separate storage facility which is not to be opened other than in the course of a bona fide criminal investigation by law enforcement, and only where necessary for such an investigation.” With their convictions expunged, the applicants likely were no longer eligible for deportation.

For good measure, Hovsepian filed a separate civil proceeding, seeking an injunction bariing the INS from commencing deportation proceedings. The court permanently enjoined the INS from deporting Hovsepian on any ground that was not in existence at the time of his original sentencing. The injunction’s practical effect is to make the JRAD a bar to any deportation attempts by the INS.

During the pendency of the foregoing criminal and civil proceedings, the applicants filed naturalization applications with the INS, and in due course, an INS examiner interviewed both Hovsepian and Ya-coubian. Before the INS rendered a decision, the applicants filed suit, requesting that the court naturalize them. The INS subsequently denied the applications, but the district court naturalized the applicants nonetheless. The United States filed these timely appeals raising various criminal, civil, and naturalization issues.

II

The government appeals Dr. Hovsepi-an’s, but not Yacoubian’s resentencing under the FYCA.1 The court resentenced Hovsepian by granting his Rule 35 motion and alternatively by granting him a writ of audita querela.

A

“District courts do not have inherent authority to resentence defendants at any time.” United States v. Stump, 914 F.2d 170, 172 (9th Cir. 1990). Rule 35 is generally the only vehicle available for re-sentencing, unless the case is on remand from the Court of Appeals. United States v. Minor, 846 F.2d 1184, 1187 (9th Cir. 1988).

Rule 35(a) provides that “A court may correct an illegal sentence at any time and may correct a sentence imposed in an illegal manner within the time provided herein for the reduction of sentence.”2 The time for a reduction of sentence has long since elapsed, Fed.R.Crim.P. 35(b), and thus the question is whether Hovsepi-an received an “illegal sentence.” An “ille*928gal sentence” is “one which is not authorized by the judgment of conviction, or is in excess of the permissible statutory penalty for the crime, or is in violation of the Constitution.” United States v. Johnson, 988 F.2d 941, 943 (9th Cir. 1993).

The district court granted Hovsepi-an’s motion because it determined it had made a “mistake of fact” at the time of sentencing. When the court sentenced Hovsepian as an adult, it issued a JRAD to bar deportation on moral turpitude grounds. Congress later added new grounds for deportation, which a JRAD does not cover. The court recited that it mistakenly thought that a JRAD would categorically bar deportation. The court stated that had it been aware of Congress’s future amendments to the immigration laws, it would have sentenced Hovsepian under the FYCA. It then would have expunged his conviction, leaving the INS with no grounds for deportation.3

Hovsepian does not suffer from an “illegal sentence” within the meaning of Rule 35. His sentence is authorized by the judgment of conviction. It is not in excess of the statutory maximum, nor is it in violation of the Constitution. The unforeseen consequences of sentencing Hovsepian as an adult do not make his sentence “illegal.” See Johnson, 988 F.2d at 943; United States v. Fowler, 794 F.2d 1446, 1449 (9th Cir. 1986). Accordingly, we must conclude that the district court erred in granting Hovsepian’s 35 motion.

B

Alternatively, the court resen-tenced Hovsepian through the grant of a writ of audita querela. “ ‘Audita querela ’ was a common law writ to afford relief to a judgment debtor against a judgment or execution because of some defense or discharge arising subsequent to the rendition of the judgment or the issue of the execution.” United States v. Fonseca-Martinez, 36 F.3d 62, 63-64 (9th Cir. 1994). While Federal Rule of Civil Procedure 60(b) abolishes the writ in civil cases, the writ might exist to vacate a criminal conviction or sentence. See United States v. Valdez-Pacheco, 237 F.3d 1077, 1079 (9th Cir. 2001); Doe v. INS, 120 F.3d 200, 204 (9th Cir. 1997). However, the person seeking the writ must show a legal defense or discharge to the judgment. Doe, 120 F.3d at 204. Hovsepian points only to the fact that the court was unaware of the consequences of an adult sentence, as opposed to a sentence under the FYCA. This observation does not constitute a legal defense to his sentence. Id. at 203 (explaining that a “legal defense” concerns a “legal defect” in the underlying sentence or conviction). Therefore, the district court erred in granting the writ as well. In sum, we must conclude that the district court exceeded its authority in resentencing Hovsepian under the FYCA. His original, adult sentence (since served) remains of record.

Ill

The government next challenges the district court’s “expungement” of the applicants’ conviction records under the FYCA. Because we have already determined that Dr. Hovsepian was improperly resentenced under the FYCA, we necessarily conclude that the court erred in expunging his records. Nonetheless, we must address the expungement question because the government concedes that Ya-coubian was properly resentenced under the FYCA.

The district court ordered that the FBI place Yacoubian’s conviction records in a “separate storage facility.” Under the court’s order, the government may not ae-*929cess his records except “in the course of a bona fide criminal investigation ..., and only where necessary for such an investigation.” The records “may not be disseminated to, or used by, anyone, public or private, for any other purpose.” Thus, the practical effect of the district court’s order is that Yacoubian’s conviction is expunged — -without legal effect — because the records are inaccessible except in the narrow circumstance of when necessary to a criminal investigation.

The district court expunged Yacoubian’s conviction pursuant to the FYCA, which provides that a court may “set aside the conviction” and “issue ... to the youth offender a certificate to that effect.” 18 U.S.C. § 5021(b) (1982) (repealed 1984). We have not spoken consistently about the meaning and breadth of “set aside.”

In United States v. Campbell, 724 F.2d 812, 812-13 (9th Cir. 1984), we squarely rejected the contention that a conviction set aside under the FYCA is without legal effect. The defendant challenged the district court’s consideration at sentencing of Ms prior FYCA conviction, which had been set aside under the statute. We held that the court properly considered the set aside conviction. Id. We explained that Congress did not intend that set aside convictions be removed permanently from a person’s record. Rather, we explained that the “set aside” provision serves the narrow purpose of “preventfing] public dissemination, and particularly dissemination to prospective employers, of an FYCA conviction.” Id. at 812. We stressed, “Nothing in [the Act] suggests that the [conviction] may not be retained for later use by another court.” Id.

We backtracked from Campbell in United States v. Hidalgo, 932 F.2d 805, 806-07 (9th Cir. 1991), where we were asked to decide whether a conviction expunged pursuant to a California statute could be used under the federal Sentencing Guidelines. In dicta, we discussed the FYCA as a “useful analogy.” Id. at 807. We explained that the Supreme Court, in dicta, “set[ ] out the purposes and legislative history of [the FYCA set aside provision] in a series of footnotes.” Id. at 807 (citing Tuten v. United States, 460 U.S. 660, 664-65 nn. 6-9, 103 S.Ct. 1412, 75 L.Ed.2d 359 (1983)). We concluded that “The Court clearly understood the term “set aside” to mean “expunged” for purposes of the Act.4 Accordingly, we stressed that set aside convictions are without legal effect and cannot be used in subsequent judicial proceedings. Curiously, the Hidalgo court did not discuss, let alone cite, Campbell.

We adopted Hidalgo’s dicta in United States v. Kammerdiener, 945 F.2d 300, 301 (9th Cir. 1991), in which we held that a conviction set aside under the Act cannot be considered under the federal Sentencing Guidelines. The court’s analysis was brief, simply stating that it felt “bound” by Hidalgo’s characterization of the FYCA. Kammerdiener, 945 F.2d at 301. Kammerdiener also did not discuss, or cite Campbell,5

*930Hidalgo and Kammerdiener offer materially different characterizations of the set aside provision compared to Campbell. Campbell stressed that convictions set aside are not stripped of their legal effect, broadly stating that they may be “retained for later use by another court.” 724 F.2d at 812. Hidalgo and Kammerdiener, on the other hand, suggested that set aside convictions carry no legal significance, and may not be used in any subsequent proceeding.

Fortunately, we are not asked to decide what, if any, legal effect set aside convictions retain. Indeed, Hidalgo and Kam-merdiener are likely irreconcilable with Campbell on this point. Rather, we are faced only with the narrow question of whether a court may order conviction records inaccessible for any purpose other than when necessary to a “bona fide criminal investigation.”6

Campbell, of course, dictates that such portion of the district court’s order is inappropriate and ineffective. Hidalgo and Kammerdiener are not to the contrary. While those cases speak to the legal effect of a set aside conviction, neither suggests that conviction records may be quarantined except for the limited purpose of an ongoing criminal investigation. In other words, while such a conviction may not be used under the Sentencing Guidelines or otherwise, it does not follow that the conviction record may be purged in the manner directed by the district court. Thus, bound by Campbell, we are compelled to conclude that the district court erred to that extent.7

We pause to note that our holding today is consistent with the view of almost all of our sister circuits that have interpreted the FYCA’s set aside provision. See United States v. Wacher, 72 F.3d 1453, 1479-80 (10th Cir. 1995) (holding that set aside convictions may be considered at sentencing); United States v. Ashburn, 20 F.3d 1336, 1342-43 (5th Cir. 1994) (same); United States v. Gardner, 860 F.2d 1391, 1399 (7th Cir. 1988) (same); United States v. Doe, 747 F.2d 1358, 1359 (11th Cir. 1984) (holding that the FYCA does not authorize destruction or segregation of set aside conviction records); United States v. Doe, 732 F.2d 229, 230-32 (1st Cir. 1984) (same); United States v. Doe, 556 F.2d 391, 392-93 (6th Cir. 1977) (same); United States v. McMains, 540 F.2d 387, 389 (8th Cir. 1976) (same). But see United States v. Doe, 980 F.2d 876, 881-82 (3d Cir. 1992); Doe v. Webster, 606 F.2d 1226, 1232-1237 (D.C.Cir. 1979). The district court’s ex-pungement order must be reversed.

IV

We turn now to the district court’s injunction that requires the INS to treat Dr. Hovsepian under the immigration law as it existed in 1985. The government argues that the injunction violates 8 U.S.C. § 1252(g).

Section 1252(g) gives the Attorney General exclusive jurisdiction to decide whether to commence deportation proceedings. Reno v. Arab-American Anti-Discrimination Comm., 525 U.S. 471, 482, 119 S.Ct. 936, 142 L.Ed.2d 940 (1999); Barahona-Gomez v. Reno, 236 F.3d 1115, 1120-21 (9th Cir. 2001). It states, “[N]o court shall have jurisdiction to hear any ... claim ... by any alien arising from the decision or *931action by the Attorney General to commence proceedings, adjudicate cases, or execute removal orders ....” § 1252(g).8 The statute’s purpose is “to limit any judicial influence on the Attorney General’s decisions regarding the commencement of removal proceedings.” Chapinski v. Ziglar, 278 F.3d 718, 720 (7th Cir. 2002); see also AADC, 525 U.S. at 485, 119 S.Ct. 936 (discussing congressional intent in passing § 1252(g)).

Hovsepian requested, and received, an injunction that required the INS to treat him under the immigration laws as they existed in 1985. The 1988 and 1990 amendments to the immigration laws made Hovsepian deportable. Hovsepian sought the injunction for a sole purpose: if the INS could not rely upon the 1988 and 1990 amendments to the immigration laws, it could not commence deportation proceedings. In other words, Hovsepian’s objective was to bar the INS from commencing deportation proceedings. As such, his claim falls squarely within § 1252(g)’s jurisdictional bar. See, e.g., AADC, 525 U.S. at 589-91, 119 S.Ct. 936 (concluding that court lacked jurisdiction over aliens’ selective prosecution claim); Chapinski, 278 F.3d at 720 (explaining that court lacked jurisdiction to compel INS to process aliens’ applications for adjustment of status because relief would require commencement of proceedings); Cardoso v. Reno, 216 F.3d 512, 516 (5th Cir. 2000) (holding that court lacked jurisdiction to compel the INS to adjust an alien’s status in an attempt to avoid a removal order). Accordingly, we must vacate the district court’s preliminary injunction for lack of jurisdiction.9

V

We turn next to the district court’s order naturalizing the applicants. The government argues that the court erred in granting naturalization because the applicants failed to exhaust their remedies with the INS.

A

Under the statutory scheme, the naturalization process commences with the applicant filing a completed naturalization application with the INS. 8 U.S.C. § 1445(a); 8 C.F.R. §§ 334.2, 316.4, 316.10. The INS then conducts a background investigation of the applicant. 8 U.S.C. § 1446(a); 8 C.F.R. § 335.1. An INS officer will then interview the applicant. 8 U.S.C. § 1446(a); 8 C.F.R. 335.1. Following the interview, the INS will either grant or deny the application. 8 U.S.C. § 1446(d); 8 C.F.R. § 335.3.

If the INS issues a denial, the applicant must typically proceed through the INS administrative process before seeking judicial review. 8 U.S.C. §§ 1447(a), 1421(c), (d). The applicant must file a request for an administrative hearing within thirty days of receiving notice of the denial. 8 C.F.R. § 336.2(a); see also 8 U.S.C. § 1447(a). The INS must schedule a hearing promptly, no later than 180 days from the date upon which the notice of appeal is filed. . 8 C.F.R. 336.2(b). The hearing officer conducts a de novo review, and may hear additional testimony and receive new evidence. Id.

If the hearing officer upholds the denial, the applicant may seek judicial review with *932the district court for the district in which the applicant resides. 8 U.S.C. § 1421(c). The district court conducts a de novo review, and must conduct a hearing at the applicant’s request. Id.; see also Nagahi v. INS, 219 F.3d 1166, 1169 (10th Cir. 2000).

B

While an applicant must generally exhaust the INS’s administrative remedies before seeking judicial review, a narrow exception to this rule exists. 8 U.S.C. § 1447(b). As stated above, the INS interviews the applicant after conducting a background check. 8 U.S.C. § 1446(a); 8 C.F.R. 335.1. If the INS fails to render a decision within 120 days of the interview, the applicant may seek immediate judicial review. 8 U.S.C. § 1447(b); 8 C.F.R. § 335.3; see also Sze v. INS, 153 F.3d 1005, 1008 (9th Cir. 1998). If the INS conducts multiple interviews, the 120 days runs from the date of the initial interview. 8 C.F.R. § 335.3.

When an applicant seeks immediate judicial review, the court “has jurisdiction over the [naturalization] matter and may either determine the matter or remand the matter, with appropriate instructions, to the [INS] to determine the matter.” § 1447(b). By the terms of the statute, the district court is not required to entertain the naturalization issue. Rather, the statute affords discretion to the district court whether to decide or to remand.

But, the district court’s discretion is not unfettered. Congress has expressed a strong preference for naturalization applicants to exhaust the INS’s administrative remedies before seeking judicial review. See 8 U.S.C. §§ 1447(a), 1421(c), (d). Congress created an exception for immediate review to allow the naturalization process to proceed without undue delay. Therefore, applicants may seek immediate judicial review when the INS fails to act upon an application within 120 days of the applicant’s interview. § 1447(b).

However, the need for immediate judicial review evaporates when the INS renders a decision before the district court acts upon an application. An applicant is entitled to a prompt administrative hearing, and may seek judicial review of a denial once a final administrative decision has been rendered. 8 U.S.C. §§ 1421(c), 1447(a); 8 C.F.R. 336.2(b). A district court should exercise immediate judicial review only in compelling, exceptional circumstances if the INS has already denied the applications. Cf. Chavez v. INS, 844 F.Supp. 1224, 1225 (N.D.Ill. 1993). Instead, the district court should ordinarily remand the matter, which, of course, would permit judicial review once the applicant has exhausted his administrative remedies.

The dissent, without citation to a single immigration case (let alone one interpreting § 1447(b)), contends that the district court retains unfettered discretion whether to exercise jurisdiction or to remand the matter to the INS. The dissent’s contention is belied by the plain language of the statute; § 1447 provides that the district court “may,” not “shall,” exercise jurisdiction. Again, the need for immediate judicial review ordinarily evaporates when the INS renders a decision before the district court elects to exercise jurisdiction over the matter.

Alternatively, the dissent contends, again without citation to an immigration case, that the INS is without jurisdiction to act upon a naturalization application when the applicant’s request for immediate judicial review is pending with the district court. However, nothing in the statute strips the INS of jurisdiction when the 120-day period has expired. Jurisdiction over the application does not automatically vest in the district court, but rather the *933court may, as a matter of discretion, affirmatively assert jurisdiction if it wishes. It would be entirely contrary to § 1447(b)’s purpose of ensuring prompt determinations to suspend INS authority while the district court decides whether to exercise jurisdiction.

C

On January 15, 1999, the INS interviewed the applicants in connection with their naturalization applications. As a result, the INS had until May 17 to make a decision.10 During their interviews, the applicants refused to answer certain questions about their background, claiming that the questions ran afoul of the court’s ex-pungement order. In light of their refusal to cooperate fully, the INS scheduled a second interview for May 6. The applicants requested a different date, and the INS rescheduled the interview for May 13. The applicants again requested a different date and the INS rescheduled for May 18 for Yacoubian, and May 25 for Dr. Hovse-pian. Both dates were outside of the 120-day deadline.

On May 18, an INS examiner presented Yacoubian at his interview with a list of questions regarding his background. Ya-coubian refused to answer most of the questions, again on the ground that the court’s expungement order barred the questions. After his interview, Yacoubian shared the questions with Hovsepian. On May 25, Hovsepian declined to attend his interview. Instead, he notified the INS by messenger that he would not answer the questions that Yacoubian had refused to answer.

On June 10, the applicants requested that the district court act on their naturalization applications, asserting that it had jurisdiction over the matter because more than 120 days had elapsed since their initial interview. On June 24, the INS denied both applications. The applicants sought timely administrative review, requesting a hearing. See 8 U.S.C. § 1447(a); 8 C.F.R. § 336.2(a).

Notwithstanding the INS’s denial and the applicants’ pursuit of administrative review within the INS, the district court determined that it would assert and retain jurisdiction over the naturalization applications. On November 9, without further action by the INS, the court granted the applicants relief and administered the oath of citizenship to both Hovsepian and Ya-coubian.

D

On the record before us, we must conclude that the district court abused its discretion in retaining jurisdiction over the applicants’ naturalization applications and failing to remand the matter to the INS. The INS rendered a decision months before the court even held a hearing on the matter. The INS missed the 120-deadline by only thirty-eight days. Indeed, the INS likely might well have met the deadline if the applicants had not repeatedly rescheduled their interviews. Furthermore, the applicants hardly presented routine naturalization applications. Not only were the applicants convicted terrorists, but the INS had to contend with the concurrent civil and criminal proceedings, which of course impacted the processing of the applications.

In sum, the record reveals no compelling or exceptional circumstances for the district court to decide the applications in the first instance. Accordingly, the district court erred in failing to remand the matter to the INS for further proceedings. The applicants’ pursuit of judicial review of *934the denial on the merits must wait until they have exhausted their administrative remedies.

VI

Lastly, the government appeals the denial of its Rule 36 motion to correct typographical errors in the applicants’ judgments and commitment orders. The government sought to change incorrect references to the statutory bases of conviction.

The court denied the motion as untimely in that thirteen years had elapsed since the entry of judgment. The court erred. As Rule 36 states, “Clerical mistakes in judgments [or] orders ... arising from oversight or omission may be corrected by the court at any time ...(emphasis added). “There is no time limit on when the district court may invoke Rule 36 to correct clerical errors.” United States v. Jones, 608 F.2d 386, 389 n. 1 (9th Cir. 1979).

The court alternatively denied the motion because the government’s proposed corrections contained new typographical errors. We ordinarily review Rule 36 motions for clear error because we usually must decide whether a “clerical error has in fact occurred.” United States v. Dickie, 752 F.2d 1398, 1400 (9th Cir. 1985). However, in this case it is undisputed that clerical errors exist in the underlying judgment and commitment orders. The district court denied the motion because it concluded that the government failed to present its proposed corrections in a proper manner. As such, the district court denied the motion as a purported exercise of its discretion. Accordingly, our review here is for an abuse of discretion, not clear error. Cf. Davoll v. Webb, 194 F.3d 1116, 1137 (10th Cir. 1999) (reviewing for abuse of discretion district court’s refusal to allow withdrawal of stipulation because it contained a typographical error); Kyle v. Campbell Soup Co., 28 F.3d 928, 930 (9th Cir. 1994) (reviewing court’s refusal to accept party’s late filing for an abuse of discretion).

The government’s proposed corrections were factually inaccurate. The motions contained incorrect title and section numbers, and the district court so found. Under the circumstances, we cannot say that the district court abused its discretion.11

VII

Finally, we stress that, unlike the dissent, we do not pass judgment on the wisdom of the INS’s decision to initiate deportation proceedings based upon events that occurred twenty years ago. The applicants arranged for a bomb to be transported on a commercial airliner, and planned to detonate it in Philadelphia, with the potential of murdering between 2000 and 3000 people. On the other hand, the applicants by all accounts have lived exemplary lives and have become pillars of their communities since their release from prison. Whether the actions of their youth justify deportation under our immigration laws is a question for the political branches of government. Judicial sympathy only functions within prescribed parameters of the law.

To summarize, we reverse the district court’s grant of Hovsepian’s Rule 35 mo*935tion and award of writ of audita querela. We reverse the district court’s entry of an order “expunging” the applicants’ convictions. We vacate the district court’s injunction requiring the INS to treat Hovse-pian under the immigration laws as they existed in 1985. We reverse the district court’s order naturalizing the applicants and remand with instructions to remand to the INS for further proceedings. Finally, we affirm the district court’s denial of the government’s Rule 36 motion. Each party shall bear its own costs.

AFFIRMED in part, REVERSED in part, VACATED in part, and REMANDED with instructions.

dissenting:

The majority opinion does everything necessary to pave the way for the INS to deport Dr. Hovsepian and Mr. Yacoubian. I cannot join the opinion, though, for it casts doubt on the holdings of two of orn-eases. Also the majority has improperly applied our “abuse of discretion” standard of review. The majority does all this to facilitate the deportation of two men who, while convicted in their youth of serious crimes, have served their time and have since led exemplary lives in the United States for many years. From this, I must dissent.

A. Naturalization of Defendants

If Hovsepian and Yacoubian have been properly naturalized, then the sole motivation for the government’s appeal — to facilitate appellees’ deportation — vanishes. The majority, of course, finds that Hovse-pian and Yacoubian have not been properly naturalized, reasoning that the district court abused its discretion when it declined to remand their applications back to the INS. I find, however, that the majority’s conclusion doesn’t make sense when I look to the relevant statutory language and take our standard of review seriously. 8 U.S.C. § 1447 gives the INS 120 days from the date of the initial interview to decide an application for naturalization; otherwise, a federal district court can step in and determine the matter instead. The precise wording of the relevant statutory section reads as follows:

If there is a failure to make a determination under section 335 before the end of the 120-day period after the date on which the examination is conducted under such section, the applicant may apply to the United States district court for the district in which the applicant resides for a hearing on the matter. Such court has jurisdiction over the matter and may either determine the matter or remand the matter, with appropriate instructions, to the Service to determine the matter.

8 U.S.C. § 1447(b). In this case, the initial interview for both applicants was held on January 15, 1999. In addition, it is undisputed that appellees applied for a hearing in federal district court on June 10, and that the INS had already failed to meet the 120-day deadline by that date. However, the majority argues that because the INS issued a letter denying appellees’ naturalization applications fourteen days later (on June 24, 1999), the district court abused its discretion by opting not to remand the matter.

What the majority fails to understand is that the INS’s denial is a nullity because the agency’s failure to meet the statutory deadline (and appellees’ request for a hearing) divested the INS of jurisdiction before it issued the denial. It is well-settled that in the instance where a federal statute directs an agency to act within a certain time frame but specifies no consequence for the failure to so act, the agency will not lose jurisdiction. See, e.g., Brock v. Pierce County, 476 U.S. 253, 259-60, 106 S.Ct. 1834, 90 L.Ed.2d 248 (1986) (finding *936that an agency was not deprived of jurisdiction because the statute failed to specify a consequence for missing the statutory deadline). However, it is also settled that an agency like the INS does lose jurisdiction to act on a given matter when Congress not only imposes a deadline but also specifies a consequence for the agency’s failure to act within the statutorily mandated time frame. See Friends of Crystal River v. United States Envtl. Prot. Agency, 35 F.3d 1073, 1080 (6th Cir. 1994) (“[W]here a statute both requires the agency to act within a certain time period and specifies a consequence if that requirement is not met, the agency will lose jurisdiction to act.”); Gottlieb v. Pena, 41 F.3d 730, 733 (D.C.Cir. 1994) (implying that an agency loses jurisdiction upon expiration of a statutory deadline when Congress has set forth a consequence of failure in the statute).1

Section 1447(b) is an instance of the latter variety; it not only establishes a statutory deadline (120 days), but also specifies in the statute itself a consequence for failure to act by the deadline (applicants may request a hearing in federal district court and the court may determine the matter), Thus, once the INS missed the statutory deadline and Hovsepian and Yacoubian filed their requests for a hearing before the district court, the INS lost its jurisdiction to determine the applications and exclusive jurisdiction over the naturalization matter resided in the district court. Only if and when the district court decided to remand the matter, rather than dispose of it on its own, would the INS again be in a position to act on appel-lees’ naturalization applications. Because the district court here never remanded (but rather determined) the matter, the INS’s denial of appellees’ applications was rendered without jurisdiction and is null and void.

Not only does the majority miss this point, it actually uses the INS’s “denial” as a justification for grafting a new and stringent corollary onto our ordinary standard of review. This is unsupported by the law of this Circuit and will no doubt leave members of the Ninth Circuit bar perplexed. I therefore feel compelled to add a few words dealing with the majority’s analysis on its own terms.

The majority states that when the INS is able to beat the district court to the punch, to render a decision before the district court has a chance to act on a naturalization application, the district court must remand the matter except in “compelling, exceptional circumstances.” Ante at 932. What is the majority’s authority for this novel (and quite restrictive) rule? A “cf.” cite to a district court decision in the Northern District of Illinois. *937See ante at 932 (citing Chavez v. INS, 844 F.Supp. 1224 (N.D.Ill. 1993)). Upon reading this decision, I must say that it not only fails to provide adequate support for the majority’s new rule, it in fact provides no support whatsoever.

Nowhere in Chavez will the reader find the Illinois district court devising or applying a rule that in any way resembles the majority’s new standard. Indeed, the careful reader would note that the words “compelling,” “exceptional,” or even for that matter “circumstances,” never appear in the opinion. Nor can the majority claim that its new rule is simply a distillation of the court’s analysis in Chavez, for that ease is factually distinguishable from ours. As in this case, the INS in Chavez missed the 120-day deadline and Chavez requested a hearing before the district court. Id. at 1224. But unlike this case, the district court decided not to hold a hearing on the merits and instead remanded the case back to the INS for a determination. Id. It was only after the INS had denied his application on remand that Chavez sought to bypass the normal administrative appeal process and seek review immediately before the district court. Id. Chavez is therefore plainly inapposite here because the district court never remanded appel-lees’ applications back to the INS, but instead chose to hear them on the merits.

In sum, the INS never had jurisdiction when it denied the applications, so there is no reason to suggest that appellees were required to exhaust their administrative appeals. And there is surely no support for the claim that the improper denial should somehow result in greater constraints on the district court’s discretion.

While I therefore remain convinced that the INS’s preemptive action is irrelevant— even on the majority’s own terms — we still must ask if there are other valid reasons that support a finding of an abuse of discretion. The answer to this question is no.

The majority makes two assertions, one factual and one eounterfaetual, that it also claims support its finding of an abuse of discretion in the failure to remand: (1) that the INS missed the statutory deadline “by only thirty-eight days” and (2) that the INS would have likely met the deadline if not for the supposed dilatory rescheduling-tactics of appellees. The former assertion need not detain us long. The INS missed Congress’ deadline by over a month (thirty-eight days) and did not act until the agency was on notice of appellees’ intention to proceed before the district court; I find no abuse of discretion in the district court’s decision not to accept the “we missed it by only thirty-eight days” defense to undermine Congress’ explicit deadline. The latter assertion, however, is belied by the record and therefore requires a discussion of greater duration.

The majority opinion gives the impression that appellees unduly delayed the naturalization process and are principally to blame for the INS’s failure to act within 120 days. More specifically, the opinion states that “the INS likely might well have met the deadline if the applicants had not repeatedly rescheduled their interviews.” Ante at 933. A full disclosure of the facts in the record, however, paints a different picture: one of the INS consistently dragging its feet and being utterly unconcerned about acting within the statutory time frame — that is, until appellees requested a hearing before the district court.

Hovsepian and Yacoubian both filed their applications for naturalization on or about August 7, 1997. The application forms stated that it routinely took approximately 210 days to process the application and schedule an initial interview. However, in appellees’ case, 210 days came and went with no date for an initial interview scheduled. On July 20, 1998 (347 days after submitting their applications), appel-lees filed a complaint in federal district *938court requesting an order from the district court compelling the INS to schedule an initial interview as required by 8 U.S.C. § 1446(a). The complaint alleged that given “the I.N.S.’s stated objective of deporting these plaintiffs (an objective that it has to date been unable to achieve), the conclusion is inescapable that the delay visited upon the plaintiffs is the result of the 1.N.S.’s desire to resolve the issues in the related criminal case [this case], thereby clearing’the way for its deportation effort.” The complaint had its desired effect; the INS scheduled Yacoubian for an interview on its own and scheduled Hovsepian for an interview after the agency was ordered to do so by the district court.

Yacoubian, accompanied by counsel, appeared for his interview on September 28, 1998. However, the INS was not prepared to proceed with the interview and told Yacoubian that the interview would be rescheduled and that he should go home. Hovsepian also showed up with counsel for his interview on November 9, 1998 (scheduled in accordance with the district court’s order), but was told, just as Yacoubian was, that the INS was not prepared to proceed and that the interview would have to be rescheduled.

The INS eventually rescheduled Yacou-bian and Hovsepian’s interviews for the same date, January 15,1999, and both men showed up again as scheduled. At their separate interviews, the INS examiner particularly focused on the failure of both Hovsepian and Yacoubian to answer Question 15(b) on their naturalization applications.2 As the district court’s sealing order was already in place by the time of the interview, Hovsepian told the examiner he could not answer questions inquiring about any past criminal activity. Yacoubian, though, did answer the examiner’s questions, stating that he had been arrested, indicted, and incarcerated, but also stating that his conviction had been expunged.

At the conclusion of both interviews, the INS examiner stated that the case would be continued, but did not indicate that a second interview would be necessary. However, some time after the two interviews and a consultation with counsel for the INS, the examiner informed Hovsepi-an and Yacoubian that a second interview would be required to obtain additional information.

The INS scheduled the second interview for Yacoubian and Hovsepian on May 6, 1999. Again, both men appeared on that date, but asked to reschedule after informing the INS that their attorney (both men had the same attorney representing them in the naturalization process) had a conflict and wasn’t able to make the interview. The INS obliged by sending Hovsepian and Yacoubian a notice on May 10th rescheduling the interview for three days later, May 13th. Appellees’ counsel called the INS examiner and told her that he had a conflict on the 13th, but could make it on May 14th — a date still within the 120-day time frame. As the INS examiner later testified, she declined the date of the 14th because she planned to attend her grandson’s track meet.

After it became clear that the 14th wouldn’t work, the INS examiner and ap-pellees’ counsel eventually settled on two separate dates. Yacoubian’s second interview was scheduled for the next date the examiner stated she was free: May 18th. Hovsepian’s second interview was scheduled on a date one week later, May 25th. Notably, both of these dates were already outside the 120-day time frame.

*939When Yacoubian appeared for bis second interview, he was handed a list of questions asking him to provide various details about any past criminal activity. On the advice of his attorney, Yacoubian declined to answer any of the questions, except the first three dealing with mundane matters. Once Yacoubian’s interview ended, he shared a copy of the questions with Hovsepian, who then decided to answer only the first three as well and sent the INS a notarized copy in lieu of showing up for his interview.3

Hearing no word from the INS, appellees filed a request for a § 1447(b) hearing in federal court on June 10th, three weeks from the date of Yacoubian’s interview and two weeks after the date Hovsepian’s interview was to take place. Two weeks later, and presumably on notice of appel-lees’ June 10th filing, the INS issued its letter denying appellees’ applications for naturalization.

On these facts, I believe it is misleading for the majority to suggest that appellees’ actions are what caused the INS to miss the deadline. Rather, it was the INS’s own actions that prevented the agency from meeting Congress’ deadline. Moreover, it is important to keep in mind that both Hovsepian and Yacoubian were profoundly interested in the speedy resolution of their naturalization applications. Both men knew the INS was trying to deport them, and both men would have therefore wanted to be naturalized as quickly as possible.

Indeed, and after all this, I am left with the feeling that the majority rushed to facilitate Hovsepian and Yacoubian’s deportation and lost sight of how we have defined “abuse of discretion.” Under abuse of discretion review, we cannot reverse the district court unless we are “convinced firmly that the reviewed decision lies beyond the pale of reasonable justification under the circumstances.” Harman v. Apfel, 211 F.3d 1172, 1175 (9th Cir. 2000). The circumstances in which the district court exercised its discretion were as follows: Hovsepian and Yacoubian were depending on the same agency that was trying to deport them to determine their naturalization applications; the INS took more time than the statute provided to make a determination; and appellees were in no real sense to blame for the delay. Under these circumstances, the district court’s decision to hear, rather than remand, appellees’ naturalization applications is not beyond the pale of reasonable justification.

B. The District Court’s Sealing Order

The majority also wrongly concludes that the district court’s order sealing records relating to Yacoubian’s FYCA conviction cannot stand.4 The order in question *940sealed appellees' conviction records and forbade anyone from opening those records except “in the course of a bona fide criminal investigation by law enforcement authorities, and only where necessary for such an investigation.” I believe the sealing order is consistent with precedent; the majority is only able to conclude otherwise by improperly casting doubt on two of our cases.

The FYCA in effect at the time of appel-lees’ convictions provided:

Where a youth offender has been placed on probation by the court, the court may thereafter, in its discretion, unconditionally discharge such youth offender from probation prior to the expiration of the maximum period of probation theretofore fixed by the court, which discharge shall automatically set aside the conviction, and the court shall issue to the youth offender a certificate to that effect.

18 ' U.S.C. § 5021(b) (repealed). After quoting the “set aside” language itself, the majority offers a categorical argument for why the sealing order in this case goes beyond the authority granted by § 5021. The majority first categorizes the district court’s order here as an “expungement” of Yacoubiaris conviction. Ante at 927. The majority then resolves what it suggests is conflicting Circuit precedent in favor of the proposition that (whatever its precise contours) a FYCA “set aside” cannot be an “expungement.” The majority then concludes that the district court’s sealing order therefore cannot stand because it is an expungement and the FYCA only authorizes the setting aside of convictions.

The majority’s argument misinterprets Circuit authority to preclude treating a conviction set aside under the FYCA as having been expunged. To make its argument work, the majority creates tension in our cases when no such tension really exists. Here’s how. The majority recognizes, as it must, that United States v. Hidalgo, 932 F.2d 805 (9th Cir. 1991), and United States v. Kammerdiener, 945 F.2d 300 (9th Cir. 1991), understand the language of § 5021 to authorize expungement of a conviction under the FYCA. Ante at 929-30; Kammerdiener, 945 F.2d at 301; Hidalgo, 932 F.2d at 807. The majority, however, then reaches back to an older case, our decision in United States v. Campbell, 724 F.2d 812 (9th Cir. 1984), and reads that decision to stand for the conflicting proposition — that “set aside” can under no circumstances mean “expungement.” Ante at 929.

In reading Campbell, I find language diametrically opposed to the majority’s reading. We stated in Campbell that “[a]l-though section 5021 provides for setting aside FYCA convictions, the expungement does not affect the nonpubhc record retained by the Department of Justice.” Id. at 812 (emphasis added). Whether looking to Campbell, Hidalgo, or Kammerdiener, it is clear that we have used the terms “expungement” and “set ‘aside” (within the meaning of the FYCA) interchangeably. See also United States v. Doe, 980 F.2d 876, 881 (3rd Cir. 1992); Doe v. Webster, 606 F.2d 1226, 1233 (D.C.Cir. 1979) (“[P]ri- or to the time the term ‘expungement’ became fashionable, Congress meant precisely that when it directed conviction rec*941ords be set aside upon the rehabilitation of the youthful offender”)

Furthermore, and even if the majority’s reading of Campbell were correct, it was still wholly inappropriate for my colleagues to rely on Campbell to the detriment of Hidalgo and Kammerdiener. The majority claims Campbell controls because it cannot hold that “set aside” means “ex-pungement” without overruling Campbell. Assuming this to be true, it is still equally true that the majority cannot hold (though it does) that “set aside” must in all cases mean something less than “expungement” without overruling Hidalgo and Kammerdiener. Confronted with this type of conflict in our prior cases, the majority has license neither to choose among them wil-lynilly nor to devise an ad hoc rule for resolving the conflict in favor of the result it likes best. Rather, and when faced with such an irreconcilable conflict in our prior decisions, we have an established protocol we must follow: the panel must call for en banc review. Atonio v. Wards Cove Packing Co., Inc., 810 F.2d 1477, 1478-79 (9th Cir. 1987).

I, of course, believe that an en banc hearing is not necessary because I think the majority misreads Campbell to preclude referring to a FYCA set aside as an expungement. I also believe, though, that the majority’s approach suffers from a more fundamental defect. I don’t think we can fully answer whether the district court’s sealing order is too broad with arguments over labels, over whether something can or cannot be termed an expungement. Rather, we must consider the purpose of the FYCA and parse our holding in Campbell to understand the precise scope of an FYCA expungement and, correspondingly, how broad a sealing order can and should be.

The purpose behind the set aside, or expungement, provision of the FYCA is to give juvenile offenders a “fresh start” once they have served their time and mended their ways. See Tuten v. United States, 460 U.S. 660, 664-65, 103 S.Ct. 1412, 75 L.Ed.2d 359 (1983) (explaining that the FYCA’s set aside provision was designed to give youthful offenders a second chance once they demonstrated that they had changed their behavior); Webster, 606 F.2d at 1234-35 (stating that the purpose of the FYCA’s drafters “is crystal-clear in one respect: they intended to give youthful ex-offenders a fresh start, free from the stain of a criminal conviction, and an opportunity to clean their slates to afford them a second chance, in terms of both jobs and standing in the community.”). Thus, we should if at all possible define the permissible scope of an expungement authorized by the FYCA to be consistent with this purpose.

Our holding in Campbell, though it allows limited consideration of an expunged FYCA conviction for sentencing purposes, is consistent with § 5021’s “fresh start” purpose. The essence of our holding in Campbell is that a prior FYCA conviction may be considered by a court when deciding on a sentence for a subsequent offense. Campbell, 724 F.2d at 812 (“Judges have broad discretion to consider a wide range of information in determining an appropriate sentence.... We believe such information may include a prior conviction pursuant to the FYCA.”). The key factual predicate for this holding that renders it consistent with the purpose of the FYCA is the fact that Campbell had been convicted of a subsequent offense, distinct from the offense that was the basis of his FYCA conviction. Id. (stating the question as whether the court could consider Campbell’s prior FYCA drug conviction when deciding on a sentence for his more recent crime of conspiracy to distribute marijuana). Campbell is therefore consistent with the FYCA’s purpose because once a former FYCA offender is charged *942and convicted of another (separate) crime, he has blown the fresh start offered by § 5021.

Importantly, neither Campbell nor any of our other cases has ever suggested that an expunged FYCA conviction may be used in the absence of this factual predicate. Rather, Circuit precedent permits looking to an FYCA conviction only where there has been a separate, subsequent crime (and even that is not permitted if the later crime falls under the sentencing guidelines). With these parameters in mind, the sealing order in this case is entirely proper. It is not so broad (as the majority would have you believe) to be in tension with Campbell, but yet broad enough to respect Congress’ purpose in § 5021.

The district court’s sealing order does not run afoul of our holding in Campbell because it does- not categorically bar resort to Yacoubian’s expunged conviction if he ever went looking for trouble again. The sealing order explicitly provides that Ya-coubian’s records may be opened and used if necessary in the course of a bona fide criminal -investigation for a hypothetical future offense. The terms of the sealing order are not overly protective because they allow access to Yacoubian’s conviction records in those limited circumstances in, which we have held the records should remain open: if they are necessary to investigate a separate, subsequent crime or arrive at a sentence for such a crime (provided, of course, that this hypothetical crime did not fall under the Sentencing Guidelines and trigger our holding in Kammerdiener).

In addition, and looking at the other side of the coin, the order’s object — prohibiting the INS from using Yacoubian’s FYCA conviction records to aid its deportation case — is fully consistent with the FYCA’s purpose. The First Circuit’s decision in Mestre Morera v. INS, 462 F.2d 1030 (1st Cir. 1972), is instructive. In Mestre Morera, the First Circuit held that an offender whose conviction had been set aside pursuant to § 5021 of the Youth Corrections Act could not be deported on the basis of that conviction. Id. at 1032. The court explained (as we have already seen) that the “clear purpose” of the set-aside provision was to “relieve [the offender ] not only of the usual disabilities of a criminal conviction, but also to give him a second chance free of a record tainted by such a conviction.” Id. The First Circuit then reasoned that making an FYCA conviction available for use by the INS was inconsistent with that purpose; indeed, the court could not “imagine a more complete deprivation of a second chance than deportation.” Id. Moreover, this is the BIA’s own position as well, for it has explicitly adopted the Mestre Morera rationale in a 1974 decision. Matter of Zingis, 14 I. & N. Dec. 621 (BIA 1974). In Zingis, the BIA reasoned that setting aside a prior’ conviction under FYCA prevented the conviction from being “used in any way.” Id. at 624 (emphasis added). The board therefore held that Zingis’ narcotics conviction that was set aside under the FYCA could not be used to deport him under INA § 241(a)(ll). Id. at 624.

In the end, the majority’s discussion of the district court’s sealing order misinterprets Campbell, casts doubt on the vitality of our decisions in Hidalgo and Kammer-diener, and fails to respect the purpose behind the FYCA’s expungement provision. Accordingly, I must dissent from the ultimate decision to reverse the district court’s decision to enter the order.

C. Conclusion

Mr. Yacoubian has been described by a California State Assemblyman as “a person of good moral character who espouses the principles of the Constitution of the *943United States.” Dr. Hovsepian has been called “warm and genuine, with impeccable moral character and ethical standards” by the Archbishop for the Western Diocese of the Armenian Church. The same district judge who sentenced both men over a decade ago for their crime has more recently found them to be of good moral character and worthy of citizenship in these United States.

Nevertheless, the INS still seeks to effect appellees’ deportation. So be it. But we are an institution of a different sort. Reason remains our currency and the majority’s effort to facilitate appellees’ deportation exacts too high a price. Thus my dissent.